Just back from 12 days in Spain ! Here's where we stayed (2 of us) and what we thought. All rooms were doubles.
In Madrid: on either side of our trip we stayed at the Best Western Hotel Villa de Barajas - right near the airport. Turned out to be a good choice since my flight into Madrid was several hours late and I was exhausted from being up for 36 hours! Cost: $115/night in December, $120/night in January. First room (#403) OK, but not worth the price. Second room (#202) was terrific. Restaurant in the hotel was pretty decent and not terribly expensive.
Hostal Las Fuentes (close to Puerta del Sol): Tiny, unheated, but clean. Entryway a disaster: cold, dark, and sandbags on either side of the hall. Staff not particularly friendly so I wouldn't stay there again. Cost: $50/night
Hostal Persal (Plaza del Angel): GREAT place to stay. Comfortable rooms, terrific staff, bright and cheerful lobby, lovely eating area for a continental breakfast (included in price) ... easy walk to Plaza Mayor and Puerta del Sol. Cost: $64/night on 12/31 and $75/night on 1/1/02 ... a really, really nice place to stay!
Salamanca: If you can afford it, the hotel NH Palacio de Castellanos is superb. A beatifully renovated historic building and absolutely everything about it is fabulous! Our room had an astonishing view of the top of the Cathedral, which was illuminated at night and was stunning. 3 nights cost us $335.00
Sevilla: Hostal R. Atenas in the Santa Cruz barrio (Calle Caballerizas). Another great place. It was small and charming. The courtyard from the street was incredible and the main lobby is done completely in colorful ceramic tiles. The staff were very nice and accomodating. Our room (#105) was simple adequately heated, and quite spacious. No TV, which was fine with us, and it is located within easy walking distance of the Giralda and Alcazar. $97/2 nights.
Granada: Hotel Sacromonte (Plaza del Lino)$97/2 nights. Good location; room comfortable but nothing special. Staff OK but not overly friendly. Within walking distance of El Alhambra and other sites.

Thanks to Madridman for hotel/hostal info - what a terrific resource.