i stayed in Tarifa just hanging out in the off season as a random place to meet my friends who chose it, agree it was a cool vibe, there were some kitesurfers but colder time of year so beaches weren't packed, nice small town to wander there were some local sites to see if you stay there but if that is the purpose of the trip not the main draw of tarifa imo..
From there took a day trip to Cadiz. i thought it was pretty comfy the old town - we just wandered around didn't enter any sites. The grand cathedral, nice city squares and parks, has some old european narrow streets, 2 city fortresses on the sea(i think from napoleonic seige?), and a nice city park(all the cities in andalusia i've been have great city parks). There is a roman theatre i didnt see. Beach access from the city but it wasn't that time of year for us.
Also did a day trip to Gibraltar - you have to ask them if you want your passport stamped. It was neat but maybe not moreso than the other options in andalusia, but being british military base there is history >>2337205
Near Seville is Italica , roman ruin settlement has a ruined amphitheatre as the most standout thing but there are statues and mosaics uncovered etc also.
Town near Seville called Carmona - has roman ruins necropolis and amphitheatre
Baelo Claudia are some roman ruins near town of Bolonia on the coast.