I'm from NYC, currently live in Japan so my info might be outdated, but RealityOne mentioned the big ones already. Aside from those two there are some big halloween places where you can pick up basics/essentials.
For the downtown/NYU area there's Halloween Adventures (also called New York Costumes) where you can pick up some nicer decks as well as the standard rider backs. They also stock some gaffed decks, boxed magic sets and other stuff as well.
In terms of performances I've heard some good stuff about Monday Night Magic (although I've never been myself unfortunately)