In reply to LastBoyScout:
How about Tenerife or, better, Lanzarote? We went with our then one year old twins to Tenerife in November, mainly for the accommodation which was villa in hotel setup, ideal for all the baby stuff. Pluses for Tenerife are the scenery and of course some climbing (though may be just bouldering if you don't have a climbing partner), minuses are that it is quite hard to escape the Watneys Red Barrel culture. Beaches generally good, if you don't mind black sand.
Lanzarote has equally impressive scenery and is much more upmarket, some of the restaurants are excellent. Beaches probably less good than Tenerife.