The two sides each pose solid arguments.
Some argue that birth sex genitals should dictate where you have the right to go, and it is as a courtesy for the others within the washroom, be it concern for safety, dignity or tradition.
Mind you, that discriminates those who were born with neither or both. (Yes there are folks like that)
The solution is simple:
Those who are POST-OP SRS/GC should be able to use the washroom in accordance with their post-op genitals, in any area of the country. I don't think that's unreasonable.
Publicly funded places should implement enough single-toilet all-purpose ( special needs / handicap / gender identity ) washroom facilities in accordance with expected volume of persons to accommodate those transgendered folks who have not had SRS/GC and I don't think that's unreasonable either for PRE-OP/NON-OP transgendered persons to comply, just to end the problems.
Privately owned businesses can do it optionally if they want business from transgendered ( and I guess crossdressing ) folks.
This would include universities, restaurants, theaters, ....even transportation which does not receive public funding.