I owned an original iPhone (bought on release day) and upgraded to the 3GS the day that was released... I loved the phone and the service, at least for me, was fine. I was with AT&T from AT&T days, through Cingular, back to AT&T and never really had any call issues, service was alright, except for the slowness of Edge. My major complaint was that I had no service at my office because of the building.
I terminated my contract with AT&T to switch to Verizon. Originally picked up the Moto Droid and then upgraded to the Incredible the day it came out. It's very iPhone'ish, similar size, weight, width, etc.
Perks of the Droid:
1. Google Voice (nuff said - this alone was worth the switch to an Android phone)
2. Market is more open than the Apple App Store. You don't have "corporate Android" killing apps for no reason at all, unlike Apple.
3. The screen looks AMAZING compared to the iPhone.
Perks of the iPhone:
1. It had a really nice hacker following. The iPhone Dev Team and everyone that works on jailbreaks and unlocks is amazing. I don't see that quite as widespread in the Android area... They're here, but it's not as mainsteam.
2. I still think that the multitouch on the iPhone is better than that on either Droid or Incredible. I still find myself having to slow down on texts and emails so that it catches my presses. Maybe I don't know what I'm doing yet with it... But I still see the iPhone multitouch as a perk.
3. Syncing/Backups seem to be easier because of iTunes. Good or bad because of NEEDING iTunes for some things is to be questioned... But it was nice to say "I want to sync these folders, these pictures, and these music libraries"... And it did everything for you.
All in all... If you go with Verizon and an Incredible, or Droid, or whatever.... You won't be sad that you did.