If you want to find the right carrier for you, you must find dealers that allow you to take a demo phone for a few days and try out. Try it everywere you normally travel. Then pick a provider that offers the sevice area that covers your daily travels. If you only travel out of town for vacation once or twice a year then I wouldn't get a national plan that costs more per month just in case you use it once on vacation. It's just not economical. However, if you travel a lot then get a national plan.
Be sure you know what roaming means.
Cell phones are more of a hobby for me than flashlights. I've been using cell phones for 11 years. I used to work for Ameritech cellular in the repair dept. until we got downsized during the Verizon merger. There are different digital technologies used by wireless carriers:
Verizon uses 800MHZ CDMA digital technology which is probably the best. Cingular uses 800MHZ GSM (they used to use TDMA)
Nextel uses a proprietary version of TDMA on thier iden network at 800MHZ.
True PCS providers like AT&T (GSM), Sprint (CDMA), T-Mobile (GSM) operate at 1900MHZ.
1900MHZ is more reflective and doesn't penetrate buildings as well as 800MHZ.
CDMA is more robust than GSM or TDMA and is the best compression method in my opinion. But a bad phone or bad network implementation can ruin all that. I know people who have phones from all of the above & are happy with them.
I live in the St. Louis metro area and have Sprint. I use Sprint because they cover were I live pretty well, so I can take advantage of my free long distance minutes by using my phone in my house. Most other carriers in my area don't have a cell tower near my house so coverage isn't as good. Also, Sprint covers all my normal travel routes better than any other carrier & they also have a cell tower right out side the building I work in. When I figure in thier service plan that works for me($30 for 300 peak & unlimited off-peak w/free long distance), Sprint is the carrier for me. I have friends that disagree though because you pay roaming charges with Sprint if you travel to a city were there is no sprint service.
Be careful with providers that claim to have a national network. Cingular, for example, claims no roaming if you are on their national network. Look at the maps carefully. Off network roaming still applies, so they don't really cover the nation. Be sure they do cover were you are going to use the phone. Some providers do offer true nationwide calling & no roam charges like AT&T but plans start out pretty high ($59.99).
Again, a demo phone is the best way to test out a providers network. If they don't offer a demo, see if they offer a 14-30 day cancellation policy. So you can drop the service and return your phone if the service sucks.
Before you settle on a phone, go to epinions.com and look up the phone model you want and find out what others are saying about it.
Don't just take a provider because the phone is "free" with them. I would much rather pay for a phone that works, and pay less per month, than have a free phone that is a POS.
Also realize that if you sign a 1-2 year contract and get a free or other deal on the phone that it's a one time deal. If you drop the phone next week and the display breaks, it's not covered under warrany and you will have to pay full retail price for a replacement. The phone's warranty doesn't cover it being dropped. You can also check to see if the provider offers insurance to cover your phone from damage (like from dropping it) or theft.
Try to get a phone that dual band, dual mode or tri-mode. You want to at least have the ability to switch to analog. Most of the coverage in the US is analog. I know that Voicestream aka T-Mobile used to never offer dual-band/dual-mode phones, so if you traveled out of thier coverage area, you were out of luck. I don't know if this has changed but it's something you should ask about.
Hope this helps.