Hallo, willkommen im Forum.

In umgekehrter Richtung wären sicherlich diese Teilstrecken interessant:

Almería - Cullera (südlich von Valencia) - war von mir eine für 2011 geplante Tour, die ich leider aber (noch) nicht realisieren konnte.

Aus eigener Erfahrung haben mich begeistert:

Padul -Almería
Málaga - Padul

Die Strecken sind radfahrerisch sehr anspruchsvoll (Steigungen, schlechte Wegbeschaffenheit), aber landschaftlich teilweise spektakulär - Radreisegefühl total...

An anderer Stelle im Forum gibt es dazu meine Reiseerfahrungen in Schrift und Bild (Verlinkung zu Picasa).

Ab Málaga würde ich auf keinen Fall an der Küste weiter Richtung Gibraltar fahren, sondern durch das wesentlich ruhigere Hinterland mit seinen kaum befahrenen Nebenstraßen.
Denkbar wäre z.B.:

Antequera - Ronda
Ronda - Ubrique

Von da aus könnte man Richtung Süden über Jimena de la Frontera und Castellar de la Frontera Richtung Süden abbiegen und auf Gibraltar zufahren.