If you go with an Android phone, I'd suggest looking around and seeing if its already rooted, or at least that it's feasible to do so (ie. no locked down/signed bootloader). Really, seriously, one of the coolest things about Android is the developer community. 99% of what I do probably doesn't require root, but it's fun to occasionally flash a new ROM and see what folks have done.
Coming from the iPhone, you'll also enjoy being able to replace the stock apps, but you will also probably not be impressed at all with the music players. I now use one called cubed (superscript 3 is the actual app title), which is pretty good. bTunes is basically a knockoff of the iPod interface, so that's there too. bTunes has better support for headset controls, as its the only one I've found that will let you triple-click to go back a track. Handcent is a little nicer looking than the stock SMS app, allows a lot more customization in terms of visuals, notifications, etc. Launcher Pro is a very nice home screen/app launcher replacement. Biggest reason I could never go iPhone now, though, is Swype. There isn't a better keyboard, imho.
Anyway, have fun.