TBH, in the beginning I myself wished that it was on Verizon instead of AT&T, but now, given the choice with everything else being equal, I'd take an AT&T one over a Verizon one. I get as good of service as anyone I know with Verizon around here, and using some speedtest.net apps to compare the 3G speed, AT&T blows Verizon out of the water.
Verizon is fast enough, and honestly if you're getting "as good" service with AT&T then you're one of the lucky ones. Almost without exception all of my AT&T friends say it sucks and they hate it. Then again, it could just be the characteristic Apple note: