Moreover, when we devalue a persons' right of privacy, where will it stop and who is to be the decision-maker of what further rights of privacy are to be dismissed? My right of privacy is no less just because I am a man than such would be for a women and each must be respectful to the other.
Um, we're discussing *public* restrooms run by, in most cases, private parties for the convenience of their patrons, right, not the one in your house. You are not required to use them if they make you feel uncomfortable. In most cases, the facilities and running of the facilities conform to a community standard for decency. But if your ideas of decency differ, you are certainly free to not use the provided facilities (I personally don't use stalls where the doors have been removed to dissuade extra-toiletal activities.) It's a fact that the standards for women and men differ in this regard. An establishment could certainly have a man cleaning the women's washroom, but enough patrons would probably complain that this would change. Apparently, not enough guys are bothered enough by the presence of the cleaning lady, and the practice continues. As I see it, you have two courses of action: take it up with the cleaning lady, and make a fuss with her bosses if she continues to stay; or be a man, pull yourself together, and use the urinal directly in front of her.