I was with the original AT&T when they were bought by Cingular. I've found that the phones used to be great, and you will get a minimum level of coverage everywhere you go (from the desert, to the mountains to the islands and everything in between), but you DO get a lot of dropped calls or "call fail" messages. An interesting side note is that with the old AT&T merged with Cingular, the coverage level doubled. Now that my phone says "at&t" again, my reception has gone down. My wife's phone is identical to mine, but for some reason it still says Cingular and she'll put her phone next to mine and have 3 bars when I have none. I can't explain this.
The Cingular/at&t plans offer a decent amount of minutes and while not as cheap as Sprint/Nextel (stay far,far away, get to that later) they do offer discounts. We can get an ALPA member discount. With Cingulat/at&t you can get a boatload of anytime minutes, plus free mobile to mobile and free evenings/weekends. The nice thing about m2m is that if most of the people you call have Cingular you will rarely use your anytime minutes. And your minutes roll over for a year if you don't use them. I don't think Verizon has that.
The problem with Cingular (now "The New AT&T") is that they DO NOT care about their customers. In my 8 years with AT&T/Cingular/at&t I have been told at least three times (quote) "We don't care if you switch to another carrier. We make our money be signing new customers and as the world's largest telephone company, you are just one of hundreds of millions of customers". This is what I encountered when I called with legitimate problems, like service interruptions, unresolved billing errors, etc. My wife was told this by the "New" at&t last month, so apparently Mother Bell is back. And Cingular no longer offers perks. With the "old" AT&T you could get a new phone every two years for free as a longtime customer bonus. Now you must buy all new phones, and their new phones are crap.
As for Sprint Nextel, their network is inferior unless you mostly stay in your coverage area. I hear nothing but complaints from pilots and FAs who went for Sprint because they were cheap. The problem is that unless you spend most of your time in large cities, you won't have coverage a lot of the time. The reception alson tends to suck unless you're in a large city, and the phones are really cheesy. You truly get what you pay for. As for Nextel my wife used to have Nextel and in addition to the network limitations, the direct connect, while convenient, wasn't always practical or used as much as expected. And it's very expensive. Regarding coverage, I COULD NOT call her on any weekday between 3 and 6 pm when she was in ATL because I always got a "trying to locate the wireless customer" message then her voicemail. The network was simply overloaded and I couldn't get through. She also got hosed by them once, because she dropped down her minutes, and they signed her up for another two year contract, but didn't make that clear. When she tried to switch to Cingular a year after she thought her contract ended, they hit her up for a $299 cancellation fee, and threatened to go to collections. They calimed that the fine print agreement they sent explained it, so they didn't have to, she "should have known that would result in a contract extension".
She switched to Cingular so that we could use the m2m since most of her friends and I had Cingular. We've considered switching to Verizon just to get away from at&t's take it or leave it customer service, but we're stuck because the m2m requires us to have about 1/2 the minutes we'd need with Verizon since all of our people have Cingular. So the m2m is a good strategy for them I guess.
I guess the bottom line is look at who you call most. If they have Verizon, go with them. If they have Cingular, go with them. Stay away from Sprint/Nextel.