I had Nextel, switched to AT&T for the first iPhone a week after it's release (got lucky as crap finding a store that had it at the time), stick with them for an iPhone 3G, then went to Sprint for the HTC Evo 4G. I'm not switching back to AT&T for the SGS3.
When it comes down to it, in my area (Raleigh, NC), both AT&T and Sprint have, minimum, acceptable coverage in most of the town. However, when you go outside of the city limits, Sprint is basically non-functional. Personally, I'm rarely in those areas though. When I had AT&T I had a similar problem, but it was far rarer.
When it comes to the customer service, they both have had ups and downs to me. Sprint stores were decent to me, but not flawless. AT&T was actually always great to me in stores. If I called for simple stuff, they were both great. When I called for some complex stuff at AT&T, they were acceptable but nothing to shout about. The complex stuff with Sprint was an absolute nightmare. Basically, I'd LIKE to say it's a wash, but Sprint pissed me off one two many times with policies and policy changes so it's not a fair fight.
Sprint's 3G speed is garbage, at best. AT&T's 3G speeds are nearly as fast as what I'd get on WiMax, too. LTE blows it away even further.
Overall, what it comes down to for me, I really want to go back to knowing my phone is usable anywhere in the world. I haven't left the country since I was 17, so it's not like it's a huge deal or anything, but it's peace of mind. I stopped turning WiMax on on my Evo because the battery life plummeted too fast, and I'm used to the 3G speeds so the upgrade will be great, too. Everything else is all personal feel or taste.
Overall, in most of the country's major markets, you're really just picking Pepsi or Coke. Get what you like. That said, if you live in a city that's notoriously bad for a certain provider, avoid it unless there's something special about them you want.