The main options as I see it are:
iPhone: you need a Mac, and you need to pay, and you need to use Objective C (possibly C# through some stuff by Novell). You have a few advantages; the hardware is all quite similar (for now), so you don't need to think about things like "what if they have a keyboard"; there are probably lots of resources too since it is so popular.
Android: you can develop on any platform, you don't need to pay, but you need to use Java. Lots of devices are available, which is nice.
Symbian: Not trendy, but very possible. I believe it is a bit of a pain to do though. See the Nokia Developers
page for official getting started stuff. I think you'll want to be coding in C (or maybe C++) for this one.
Pre: I don't know much about this one, but there is a Palm Developers
Maemo: This is another Nokia one, only just starting to go mainstream. In terms of developing applications for it... it is an absolute dream. I "ported" my own desktop project to Maemo, and it took about 5 minutes. The OS is a debian derivative, so you don't have to fit with whacky mobile frameworks. They come with python out of the box, but you can compile C or C++ stuff for it easily, install ruby, or whatever. You will want an N900 (probably quite expensive if you are used to subsidised phones, and a bit expensive otherwise), though you could also get an older device (not a phone) like an N810... they are a lot slower though.