Verizon has great service and coverage. Welcome to the Big Red! Droid X is a good choice too.
I love my iPhone and it is not going anywhere. But the fact is that on several occasions my wife, who is using a BlackBerry on Verizon, had a good signal and could make calls whereas I had the lovely "No Signal" on my iPhone. Not happy about it at all, but I still wouldn't trade my iPhone for other handset. Though I very much hope that at&t continue investing in their wireless network infrastructure.