Okay, yes, Cingular had a questionable reputation, to the point that I teased a coworker about her Cingular personal phone. She was defensive of it, said the coverage was fine.
A little while later, my job gave me a Blackberry right after Cingular became AT&T, and I quickly noticed that everywhere I went (DC, NC, NY, MD, CO, NorCal, Vegas, Arizona ...), my cell signal was as good as or better than what other people had.
I'm not saying AT&T has the best network, maybe Verizon still does.
My point is that people are making logical errors when they believe Apple made a poor choice in networks. Whatever network they'd picked, the same two actual factors would still be true:
1 - some people will have poor coverage due to where they live or work. This is true of all carriers.
2 - adding a big number of smartphones that are designed to consume media will put burden on towers and equipment in population centers.
But it's easier to just say "AT&T sucks."
fwiw, I assumed I'd have a lot of issues with a T-Mobile phone, since that's clearly one of the smaller of the national networks. But my T-Mobile service has also been pretty good everywhere I've been. I'm starting to think they're really all about the same these days.