There are some great cities to visit in the Spanish Extremadura - eg Salamanca, Mérida. Though equally Lisbon is worth anyone's time. If you have a bike with reasonably wide tyres you could consider going south along the Vía de la Plata (an ancient route from Sevilla to, IIRC, Ourense).
the only problem with the western option is you can't route via Córdoba and Granada. But you could hole up near Sevilla and then go on the train.