They are apparently releasing an Android phone on Verizon later this year: http://www.engadget.com/2009/07/30/motorola-sholes-android-p...
I'm definitely going to be watching that. I have an iPhone 3G right now and am fairly happy with it -- but I would really like to take advantage of Google Voice's voicemail transcription, as I'm deaf and if works even halfway decently it would be a huge thing for me.
That, and I do think Android does notifications (the drag-down notification panel) far better than the iPhone does. The potential sticking point for me is that for work, I need Exchange support that's at least as good as the iPhone's.