Cellular data speeds in New York really are slower than other metro areas in the country (as Kevin points out).
I benchmarked an iPhone 3G (with full signal strength) and a Verizon UM175 (EVDO Rev. A) on my laptop. I tested with this app [iTunes] for the iPhone and this site on the laptop.
iPhone 3G: 342/104
Verizon EVDO: 1106/485
iPhone 3G: 905/80
Verizon EVDO: 1987/489
(Speeds are measured in kilobits per second, down/up.)
Best guess for an explanation: Congestion on the New York infrastructure destroys any chances of high speeds most of the time.