The phone you use is as important as the service you have. A bad phone will drop calls, have bad reception, waste battery, and have difficult to navigate menus. It's important to research phones (C|Net reviews and user opinions ar required reading).
That said, I use Verizon. I use it in New York City as well as countrified areas like Pocono Lake, Pennsylvania (the middle of nowhere, on top of a lonely mountain...) and the service is pretty good no matter where I am.
Customer service is pretty good. I've called a few times, usually just to get questions about features answered, and the reps are friendly and know what they're talking about. I haven't waited too long on hold, either. FAQs on the Verizon Wireless
website are also useful.
My sister uses T-Mobile, and her experience is just about equal to mine. It's tough to quantify, but the general feeling is that her reception is a little bit worse. Not by much, though.
FWIW, my parents have old Verizon accounts -- so old that the Audiovox phones still say Bell Atlantic on them. The service still works fine on their phones, too.
I haven't used any special features like email, txt messaging, or pics. They cost too much to be worth it, imho.