The current Galaxy Nexus and several other phones handle both AT&T and T-Mobile's 3G frequencies. You are right, however, in that a lot of phones won't.

Those are pretty much your only options on the GSM front. T-Mob has a 30 USD/month plan for 100 minutes and unlimited text/data, but all of their other plans are more expensive than straighttalk for smartphones (probably featurephones as well).