Many people complain about their coverage and the usability of AT&T, but when you do have a signal and the network is not cluttered, PCWorld found AT&T to have the fastest network by far. In their comparison PCWorld tested all four major carriers. T-Mobile was found to be the slowest with an average of 719kbps despite their recent increase in network speed. Sprint came in third with an average of 851kbps. Verizon averaged 1075kbps and AT&T average 1259kbps. The test was done in thirteen cities and then averaged together to get the speeds.
From my own experience in upstate NY I would have to say I have found these statistics to be correct. When comparing download speeds on a Verizon Palm Pre and the iPhone I found speed tests to indicate and average of 1200kbps for AT&T and 900kbps for Verizon. This may not be true for your location, and if not what do you average on your carrier?