I used to have an iPhone and iPhone 3G. I now have a Nexus One. Plain vanilla Android is fine if you are a bit of a geek like me, but if you are someone like my fiance who has no interest in computers and technology then I would recommend the HTC Desire or the iPhone. The one major advantage of the Nexus One is that it should get updates faster rather than having to wait for HTC.
Hardware wise they are both pretty much the same, although I do find the iPhones touchscreen slightly better than the Android screen, the iPhone just seems to track your fingers more accurately and the Android phones sometimes go a bit AWOL but normally locking and waking solves the problem.
You can't go far wrong with either. If price is a factor, then go for the Android phones. If not then go check out the iPhone 4, HTC Desire and Google Nexus One (the Nexus One is exclusive to Vodafone unless you buy it unlocked at $529 direct from Google).
I do miss my iPhone a bit. Android is not as slick and polished. However, pretty much all the problems I have are software related which I am hoping and sure Google will fix pretty quickly and the Market is growing.