I live in Australia with a fully unlocked Android handset. I pay $16 / month for my no contract dumb pipe and that's that.
Android has nothing to do with the issue that the OP hates...
What makes an Android phone easier to get a hold of compared to a iPhone? Both phones are $500+ if you get them standalone.
You referenced Nexus S with ICS so I thought we were comparing that to the iPhone.
I was regularly inquiring about android handsets for the last couple years. There were still carrier exclusives (for x number of months), and no one would sell me a high-endish, unlocked handset (e.g. Galaxy S).
The easiest way to get an unlocked Android handset is buy it online (be careful you get correct handset variant).
If manufacturers weren't capitulating to carrier demands silly things like this would not happen.
If you want an unlocked iPhone you go to an Apple store and just say so and it works on all carriers.