Get something that runs Windows Mobile 6. As far as phones, I'm hopeless (I couldn't care less about phones, a cheap $15 one for emergencies is all I need), but I have a Windows Mobile 6 PDA (non-phone) and it owns. With WM6 and an Internet connection, you can browse YouTube, the Internet, watch movies from flash cards, play MP3, chat online, do e-mail, edit documents, pretty much everything. BlackBerry phones can't do much in terms of multimedia (YouTube is out of the question, minimal mp3/video support at best) but they're great for e-mail and business stuff. I'd stay away from anything that uses Palm OS because it's very dated and doesn't do much compared to WM or other newer OS'es.
