I would seriously look at an Android phone.
The HTC range in particular work really well as phones at least as well as an iPhone.
Google has put together a really well thought out framework and SDK which well put together and well documented, the only downside seems to be that you need to install the bloatware that is eclipse.
Most of the HTC phones support UMTS, EDGE and Wi-Fi so you have lots of connectivity options. You usually get GPS, motion sensors and "Haptic" included. All of which makes for a million possible apps.
Also you can juts buy the phone and insert your SIM. No need to marry AT&T or divorce your current provider.