...kk49827...gosh, what a loaded question!!..
So much depends on what you and your good lady would like to see or do and how you want to travel, i.e. fly and/or drive.
Let me throw a few names into the hat. Rome, Majorca/Ibiza,Barcelona,Andora,Gibraltar,Sevilla,Canarie Islands and Lisbon (as you mentioned). A number of these that i have listed will be cold in Jan...but then so will Madrid!!