Málaga, Córdoba and Cádiz
Málaga is a very nice and big city.
Córdoba have a muslim mezquita which is worth of visiting.
Cádiz is a small city surrounded by water, but it is charming (in Cádiz I may suggest to restaurants: el Ventorrillo del Chato and specially El Faro).
Near Cádiz there is a abandoned fishmen village which is great: Sancti Petri.
Near Granada you have the Medina Azahara summer palace, with the same style than the Alhambra.
Probably someone may suggest some villages in that zone. Andalucía is just so huge and has so many places to go...
Fernando