Oh well, the author can only blame himself. First, try wrapping the terms in quotes: "cheap hotel" in "new york". Ignoring the sponsored links (which should not be ignored, since they are actually what he's looking for), the first link goes straight to a page where you can make a reservation. And if that site doesn't look trustworthy enough, it's only a click from there to travelocity.
Second, I don't know about actual hotel owners, but just imagining myself as one, I know I wouldn't advertise my place as "cheap". Cheap is nothing to be proud of. Try "budget" or "inexpensive" or other, more elegant synonyms, and you'll fare better.
Third, forget about the basic search. Go to Google Maps, use the exact search phrase they give as an example: "hotels near <location>", and you'll get locations, reviews and hotels' own pages with pictures, descriptions and reservation info. No spam, no linkfarms at all.
Google may have issues, but inadequate search results is not one of them