AT&T sucks badly in NYC. Sometimes I get roaming charges in my apartment because it can't connect to any of the local cell sites (yet Phoenix and most of Tampa were considered local with a Brooklyn cell area code...) When I get a signal its between 1 and 3 bars, never 4 or 5. Disconnects and line noise are pretty frequent.
Verizon seems to be THE choice for cellular here, no contest. Even though their land lines absolutely suck and they can't successfully install DSL in anything less than 8 months.