Pay toilets are super annoying, and very common in Europe. Still, even if you are in NYC, it's hard to find a "free" toilet. Most of the time you have to go to a restaurant, buy something, and then you'll get the key.
Sure, in theory there could be wonderful tax-funded public toilets everywhere, but it's a hard sell to taxpayers: most of the time, locals aren't the ones getting caught in need of a bathroom. (I mean, how many times in your typical day do you use a public toilet? Probably not often; it's a thing you use when traveling, or as a tourist in a different city.) And thus they're understandably reluctant to divert tax money to pay for them, and they get to make the call.