We had the opportunity to spend 3 wonderful weeks meandering around. Our trip was definitely enhanced by all the great info and research I was able to do on this website prior to leaving. So thanks to MadridMan and all the others who contributed!!
As a footnote, I work for Hilton Hotels and when given the choice I prefer the personalized feeling of small properties, but I also evaluate them based on hospitality standards. All properties had staff that spoke English and took credit cards.
Madrid - Hostal Adriano. As I remember seeing somewhere, either you get it or you don't. This place personifies what a hostal should be. The rooms are clean, fresh, comfortable and make you feel at home. The staff is friendly, helps with luggage up the stairs, making recommendations, etc. Our double bed room had a small fridge, corner desk, digital safe and adequate clean bathroom. Nice sitting areas in hallways. The location cannot be beat as you can walk to many major sites, the museums, and the bus line to Segovia. 55€ per night, http://www.hostaladriano.com
Barcelona – Hostal Goya Principal. We stayed in a room in the newer section. Our room was large, had a comfortable bed, adequate clean bathroom, writing desk and a door that opened onto an interior courtyard. There were no safes available but the front desk would secure items for you. There was a sitting room in both sections with a TV, self serve hot water pot with complimentary coffee and tea. The location is in a nice safe quiet street just north east of Playa Cataluna. Easy walking distance to Las Ramblas and other sites minus the noise. 80€ per night http://www.hostalgoya.com/
Sevilla – Hotel Alcantara – This is smallish hotel a block or two from the Cathedral on a narrow pedestrian street. It looks fairly new inside, standard type rooms that are clean and comfortable with an elevator to all floors. The hotel has a self serve breakfast for and additional 5 euro. The location was the great as it is centrally located. 70€ per night. http://www.hotelalcantarasevilla.com/
Granada – Hostal Atenas – This was the only place we stayed that we disliked. The rooms make you think of dormitories with minimal furniture and a heads in beds mentality. The beds were metal cots with foam slabs that squeak when you move in the slightest. We were checked into one room with 3 twin beds that was as dark as a tomb and musty with an extremely moldy bathroom. We requested another room and were put into one with 5 twin beds that wasn’t as dark and had a cleaner bathroom. However the bracket that held the shower sprayer was broken. We had to request to have the power to the A/C turned on daily and we had to leave a cash deposit to get a TV remote. The central location was convenient and they did have parking available at 11€per night. There were 2 pc’s with internet access available for minimal charge. 55€ per night. http://www.hostalatenas.com
Malaga – Hotel Ibis. We selected this hotel based solely on its proximity to the airport as we had an early flight out the next morning. It is a clean, comfortable standard hotel with an on property restaurant and complimentary parking. Nicest bathroom of all places we stayed. 45 € per night http://www.ibishotel.com/