I don't think the pain is limited to Linux. Sometimes I don't even bother using the wifi at these places even on my rather vanilla android phone/tablet. Often

I don't think the pain is limited to Linux. Sometimes I don't even bother using the wifi at these places even on my rather vanilla android phone/tablet. Often captive portals will restrict certain kinds of traffic (e.g. by blocking ports) just "because". However, bear in mind there are financial incentives and ramifications to "free internet". So, every provider tries to lever things in one way or another; this includes cell-phone companies and ISPs themselves. DNS hi-jacking is a good example. All that said, the combination of ways networks can be configured (both yours and that of the captive portal) are enormous. And, most likely this is what's causing the pain... I empathize. In this specific case, if you're not already doing so, I'd consider trying a tool which could help at certain locations/providers. I've heard good things about Gnome's network-manager-applet. And, like you say, keep your phone's hotspot nearby just in case.