Ese mapa tiene poco detalle para ver eso: los saltos de color son de 3 grados.
En todo caso los datos de AeMet son muy concetos, de las capitales y poco más y no dejan ver algunas particularidades que se dan en pocos km por las distintas orientaciones, orografía, ect.
Como ves, de las capitales Huelva que es muy atlántica y la más cercana al Algarve es de las que mas frio hace en Enero, sobre todo porque bajan más las mínimas.
Por eso me inclino más hacia el Mediterráneo, que en esta zona tiene una temperatura similar al Atlántico en su extremo sur y las costas, más montañosas, cortan el paso a los vientos del norte, limitan el enfriamiento por radiación al no ser grandes planicies, recogen más sol en las vertientes sur y además (para el windchill) sopla menos el viento.
De la que has puesto la mayor es Tarifa, pero con una sensación térmica bastante menor por el viento y humedad. Si hubiera datos fiables de Motril, Nerja o Marbella puede que igualen los de Tarifa pero con mejor sensación.
Concretamente en el caso de Málaga te puedo decir que llevo años midiendo en Fuengirola y siempre tenemos de 2 a 3 º más que en el aeropuerto (y vivo a las afueras, en el campo). Y más suave aún es la zona de Calahonda, muy "oceánica"