disclaimer: I'm an avid Android user and own Galaxy S2 GT 9100
If you want your phone just to work and you don't like mess around much with various setting, tweaks etc - get an Iphone 4S - with new plan (or upgrade) it's not that bad
However if you value freedom - get Samsung Galaxy Nexus on verizon or if you stuck with ATT but still want the Nexus - you'll have to cash $650-700 for gsm edition.
Nexus is currently the best android smartphone and imho the best smartphone period.
However Samsung Galaxy II phones have a lot to offer as well and they available on both AT&T and Tmobile with discounted for new customer.
Galaxy S2 offers a bit better camera than Nexus and upto 48gb of memory, but it lacks the newest Android OS - Icecream sandwich
I have nothing good to say about Windows phone so I'm not going to say anything
