If the toilet is gender neutral, than protective Dad dude should have absolutely no problem with this policy. If he's really that worried about lurking creeps spying on his daughter in the Bathroom he can always just go with her.
I don't know how it's handled in america but over here it's pretty commenplace to see parents (reagrdless of gender) in either restroom with their children (also regardless of gender).
It's also pretty common to see girls in the guys restroom if the line for the girls room is too long and no one bats an eye. (Vice versa is more uncommon because usually there never a line in front of the mens restroom, but I've seen it happen at small venues as well.)
This shouldn't be an issue.
That's parents. I'm concerned about my wife going into the bathroom and some 350 pound rapist goes in there after her. There comes a point when, regardless of your opinion or beliefs (or lack thereof), we have to weigh which rights are MORE important.
The rights for freedom (choosing bathrooms or abortion for your own convenience/desire, for example) or the rights of safety/life (my wife's safety from rapists or a babies right to life, for example).
We HAVE to prioritize otherwise we risk harm and death in the hope of achieving more comfort for a incredibly specific and small portion of the human population.
Thing about that is, if anything, the laws in NC made such a scenario so much easier for actual perpetrators now. These laws force people who look, sound, walk and probably use the loo like men use the womens toilet (and the opposite for transgender women in the mens one). Perpetrators don't go through great lenghs to commit their crimes, they commit them where and when it's convinient. And it's much more convinient to pretend you're a transgender man as a male than it is to pretend you're a transgender women.
Genderless or unisex bathrooms on the other hand solve that issue because, since everyone can go there, who's to stop you and an couple security guys to go in as well and check on your wife and her would be rapist? That's right, no one.
And as others have pointed out a stick figure sign is not usually deter a rapist. A restroom full of suspicious women might, but since seeing perfectly male looking guys in the womens restroom should be an expected occurence now, it makes it easier for the hypothetical perpetrators.
I'm sorry if I sound neglegent on the issue, but as someone who has used mens, womens, unisex and even group restrooms I don't see the issue. (and yes, the group one was wierd, but you get used to it)