Lanzarote, loved the diving. Did my OW there (with Calipso) and went back 6 months later for another holiday. Mala (North) I reckon was one of my most memorable ever. Car hire and food is cheap, there are other things to do on the Island apart from diving. I believe there is a cave network there as well that is a memorable dive, although i dont know how you get to do those. TerryH on Bsac and Divernet webs might know. Would I recommend it - yes, but outside the main summer hols period.
I'm no marine expert but we saw rays, angel sharks, barracuda and a host more stuff to boot. Water temp about 18 so a semi will do and viz was like for ever.
Calipso didnt hire ponys but the link below is a new outfit, I havent used them, that seem to think ex Brits need ponys so supply them
I did my try a dive in Fuerteventura, then got certified over here and went back for some real diving. Dived with H2O diving which is owned and run by a BRITISH guy. http://www.h2o-diving.com/uk/00.htm