Hey,
I worked in NYC between undergrad and my masters, and moved there from Toronto. Hopefully I can answer your questions.
1. I found my place on craigslist, and I guess I was searching for a room with roommates, but no one seemed to mind that I wasn't an American... though, I had lived in the US before so I did have a credit history (usually the real hitch). If you are a US citizen, perhaps that'll be enough?
2. I wrote month by month cheques as they were due (and just rented a place in Rochester, NY with the same policy). Instead you usually have to sign a year long lease.
3. I was never asked for a guarantor (same is true for my current situation). Are you looking for places through a broker or something?
4. I found it difficult that in NYC people only need to give 30 days notice; since I was away at a conference a month before I needed to move this was particularly troubling. I also found a lot of places to be very expensive AND very terrible. Though, the place I found in the end was nice, and most of my friends lived in nice places (though, I don't think I met anyone other than profs / people with awesome paying jobs who found places that were roach / mouse free...). That was definitely a shock.
Finding a place in NYC is rough. Finding a reasonably priced place in the city is possible, people have done it; it just may not be easy. Also, you might want to check this out: http://www.dnainfo.com/new-york/crime-safety-report/