I don't know if they've changed but a couple of years ago Dreamhost were dire - stay away. Also stay VERY clear of the likes of GoDaddy, HostGator or any other host owned by Endurance International Group. You can get a (rough) list here: http://en.wikipedia.org/wiki/Endurance_International_Group
Whichever one you pick, do a search for them on WebHostingTalk and go off recommendations. There are so many bad hosts out there, or hosts started by people who think they can make a living off of it, only to sell up a year down the line when they get bored of it.
Do you require NYC/Metro or would Buffalo NY still fit your needs? If so, feel free to PM me and I can give you a few sites to test loading speeds that have several million posts each hosted off our Buffalo NY shared hosting servers. I also can offer you Atlanta GA if your just looking for somewhere on the east coast.
Maybe I don't understand, but what difference does it matter where the server is? I had very specific needs for my server setup (not running XF) and went with Hostek. I honestly have no idea where the servers are. They work, they are fast, service is excellent.
You want the server to be in a datacenter close to your audience. So if you run a forum about Australia, the site should be hosted in Australia instead of the US or EU as it'd be slow as hell for the primary audience.
If you've got a 'generic' audience, the US East Coast or Europe is usually be best place to be as the peer points in these two areas are very well spread out. Take a look at this and you'll see what I mean: http://www.submarinecablemap.com/
That part I get. But will the average user notice the difference in speed for a server in different parts of the same state? Before I moved to Hostek I was hosted in Arizona. I live in Massachusetts. The speed was great for me. Now I'm with Hostek and have no idea where my server is and the speed is still great.
Nope, you'll likely not notice that. It's more long-distance you'd notice. There's no benefit to having your server in the same state at all really. I'm in the UK and have a bunch of servers on the east coast and speeds arent an issue at all. West coast connections are marginally slower, but nothing major.