Had some friends stay in New York and have used AirBnB quite successfully.
If not, the W Hotel on Lexington has been reasonable. Keep in mind all hotel rooms in the budget range are always very small in New York.
http://www.thegothamhotelny.com is a very cool hotel with a great location for walking.