la paz hotel halem, hotels and food
Price: US$12.5 (with private bathroom), Cleanness: Acceptable
Hotel Alem seemed to be the best choice for non expensive mid range hotels. I have met several people in later part of my trip who also have lived in this hotel.
If it is full, you can try Hotel Sagarnaga which is next to Alem. It is more expensive but if you bargain, you can get a lower price than Alem (you don't need to know Spanish to bargain, just remember the magic words "mas barato").