I would stay with Verizon. Opinions vary on this, but I'll tell you mine: I had AT&T for 3 years (I came over from Sprint, which was actually pretty decent) and the reception & dropped calls were sub-standard. Clearly this will depend on where you live, work and travel, but my experience was a poor one.
I moved from an iPhone 4 with AT&T, to the same device (iPhone 4) on Verizon, and the difference is like night and day. It really surprised me as I thought that perhaps my poor experience was due to the phone itself. I travel for both work and play, so I've had a chance to try out the iPhone 4 on both services, in quite a few different states.
Again, a lot of this depends on where you spend your time etc, but I found that the stereotype for both AT&T and Verizon generally rang true, AT&T usually had significantly faster data speeds, where as Verizon had noticeably better signal/reception, fewer dropped calls and a more extensive area in which I could get (albeit slower) 3G data service.
Experiences and opinions will vary about this sort of thing, but those were mine and I hope it is helpful.