Ok, bear in mind I have not checked the train connections.
Fitting your last point - Cordoba or Granada. Both have some amazing sites. Easy enough to cover in a day or two. All walkable.
On the coast, Malaga? Or any of the many little towns near by including Marbella. I just don't know logistically how easy it is to get around in those places without a car.