I use Verizon, and have travelled to several places in the upper U.S. with my phone. Aside from local quirks and problems with the antenna breaking on my goofy phone (Motorola StarTAC), I've been pretty happy with it. I can almost always get service, usually digital.
I live in Milwaukee, service here is good. Some of the ritzier suburbs are a treat because the residents don't like cell towers in their neighborhoods.
In Chicago I get pretty lousy service in downtown, especially inside or around the tall buildings. But, the rest of the city is good.
I get good coverage all over Wisconsin, and northern Illinois (down to Peoria).
The U.P. is a virtual dead-zone. Analog only except in Escanaba, where I found one tower that I could make clear calls from.
Service is good along I-90 all the way to Schenectady, NY.
The west coast: Seattle, WA to Cresent City, CA was covered very well. I think I might have had better service there than I do in my home area. I was amazed at my coverage along I-5 in Oregon. I even placed calls from Crater Lake. After having to find a window to place calls in Chicago, I found that quite amusing... "Can you hear me now?"
Long story short: I think my Verizon phone does the trick, but ANY CDMA should give you comparable results. The real test is in how the provider treats its customers. I still complain about my phone when the service is less than perfect, but I'm not planning to switch.
AK