I'm in DC/Northern VA and have been on AT&T, then Cingular, then the "New" AT&T. I'd say service got worse when they become Cingular, with slow, steady improvement since. AT&T isn't horrible overall. Generally, things work as expected, but I've definitely had sporadic poor service.
I got the 3G on launch day and noticed that in some areas I'd have full 3G reception, but data would not work at all. Then, about a week later, it worked great. Once in a blue moon I'll have a 15 minute span where most of my outgoing calls fail and connected calls drop. Then things will settle down again. That seems to happen less and less. It feels like AT&T is a victim of its own success. I'd like the service to be better, but it's good enough, given that the iPhone is the best mobile device I've ever used, and by a wide margin.
I've been in SF for weeklong trips, and service was worse. No dropped calls, but data was often slow, especially during Macworld Expo. AT&T's service doesn't seem to scale well. I've heard horror stories about performance in NYC.