I think Verizon has the best service overall. I have had ATT and Verizon, and currently I can definitely say Verizon is the best. My brother switched from Sprint to Verizon, he is much happier now. ATT, Cingular and T-Mobile are all on GSM network and currently the service is spotty. It will be a few years before they have better coverages. I don't know enough about Nextel to comment.
One caveat, however, Verizon's phones overall are not pretty and not a good selection. I also recommend a tri-mode phone (as opposed to all-digital) as it covers both digital and analog service areas. Here your choices are down to about 5 or 6 phones.
Looking to change cell providers, but just don't know who to go with. I currently have sprint, love their service but hate their phones. Who has the best service in NYC?