- Symbian (Nokia S60/Sony-Ericsson UIQ) - Windows Mobile (various flavours thereof) - Android (No real hardware yet available) - Non-Native development (J2ME et al.)
The best way to get started would be to download an SDK for one of these environments. They all come with emulators, so you can start playing around with writing apps without any investment in hardware.
I'm not from the USA, but I've spent most of my working life in the mobile industry so I believe I know what I'm talking about. In the USA, only certain places have GSM networks. This includes most of the major cities, San Fran, New York, Atlanta, LA, etc. Pretty much any Smart Phone you can buy is a GSM phone. There are a few exceptions, some of the older Palm phones were CDMA, but Palm is essentially dead now. Before you buy a new phone, just make sure your current network is a GSM network. While I understand it isn't a terribly common thing to do in the US, most developers will buy development phones unlocked direct from the manufacturer (or a reseller) and put a SIM they already own in it. In the UK, you are pretty much drowing in SIM cards. Both Orange and O2 give away pay as you talk SIM cards on a regular basis online, and I tend to grab as many as I can on each occasion, since they tend to get deactivated after a while because they sit in various of my phones not getting topped up.
As for what phone to buy, wanting GPS limits you a little. I'd recommend the Nokia N95 8GB as a good start. It's a Symbian S60 phone with built in GPS and WiFi.