The S3 is definitely worth its price if you plan on going into a contract. Unlocked, and no contract, a Galaxy S2 should be good prices by now but the international version only works in EDGE with T-Mobile (it does with 3G with AT&T). It would be good if the S2 has been upgraded to Ice Cream Sandwich by the previous owner, but its not a problem if you initiate the upgrade process yourself.
Somewhere in between, there is the unlocked, unsubsidized Galaxy Nexus in the Google Play store. Brand new, but at $399 that's pretty cheap for an unlocked unsub phone of these specs. It will work on T-Mobile's 3G right up to 21Mbps.
I am @guamguy on Twitter.