Trying to build first fixie?
I think you're confusing a fixed gear with a single speed. 

A single speed bike can have a fixed gear (the cranks must (things the pedals are attached to) turn whenever the rear wheel turns), or a freewheel (you can coast, i.e. not have the cranks turn when the rear wheel turns). Luckily, a lot of fixed gear bikes have so called flip-flop hubs, where one side is fixed gear and the other side has a single speed freewheel.

For a single speed freewheeling setup, you can take any frame, put on a single speed wheel and if it doesn't have horizontal dropouts (or eccentric hubs), attach a chain tensioner to it. For a fixed gear setup, you need horizontal dropouts or an eccentric hub since you'll snap a chain tensioner in a fixed gear setup while braking. 

Generally, the economical ways to do a fixed gear are starting with an old road bike (say 80s, which has horizontal dropouts) and putting a flip flop hub wheel or fixed gear wheel in, and adjusting the chainline, or buying a bike which is already fixed gear (or has a flip flop hub). Since fixies have become fashionable these days, the latter is usually the  easier option. 

Building a bike from a frame and components is possible, but you need to check compatibility and sizing and everything on your own, which judging by the wording of the question, you do not have. 

I would recommend getting an already assembled single speed bike with a flip-flop hub. That way, if you find you don't like fixie-ness, you can flip the wheel and get a usable single speed with freewheel. You can also have two gear combinations (though a bit hard to switch between them given that you have to swap the wheel) this way. You can also probably walk into one of many bike shops in the NYC area and figure out a single speed which fits you well easily this way. I would also recommend having a front and rear brake installed on the bike, even if it is fixed gear only -- it may not look "cool", but it can easily save your life in NYC. 

Also, these links from Sheldon are essential reading, especially if you go the build your own route.