I switched to AT&T specifically for the iPhone -- and so far, AT&T's coverage wins hands down over Verizon. Perhaps it's just my area but this blanket "AT&T is crap" statements are total bullshit.
I have AT&T in the St. Louis metro and their service sucks badly for me.
Granted your phones make a difference, but it is completely unacceptable when I am traveling on the metro system (which is outside over 95% of the time and I can't stay on a call for the 25 min trip.