Definitely go with an Android or an iPhone. Anything else is just not worth it, unless you're strictly a text/talk phone person.

Another thing I like about my iPhone is that I use it as an iPod. I have an iTouch that holds a ton of music, but my iPhone is set to hold music from certain artists, plus any new music I download, so I always have my favorites to listen to, so I don't have to lug the iTouch around.