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 site with details. I believe it is very similar to doing web app development (i.e. you code with html, css and javascript)... though I'm guessing there is also some way to write native code too.
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.