I'll second the hostels, and don't dismiss them just because apparently in the US they imply bunk beds in large rooms. I've stayed in hostels quite a bit, and every one had places rented by the room, not by bed, and plenty of single and double rooms.

Hostels, at least in (most of?) Europe, are essentially cheaper hotels, usually without a minibar and with much less upselling. Or, in terms I know from US cinema, they're like motels without the car culture aspect.