Well, have a look at Hoteles Maestre. They run a Hotel, a "Hostal" and some apartments. All them are located in the same street, in the old quarter but near to modern downtown. They are nice, convenient and reasonably priced. Despite being in the old quarter, they have parking facilities.
I am a local and I have heard positive comments about them.
Their website is:

http://www.hotelmaestre.com/principalingles.html

In Google Maps:
http://maps.google.com/maps?f=q&hl=es&geocode=&q=hotel+maestre...