I generally recommend OpenStreetMap as a source of reasonable quality, free mapping. Have a look at
http://www.openstreetmap.org/?lat=28.271&lon=-16.556&zoom=11&la... and judge for yourself whether the quality is good enough for your needs.
There are a good number of handheld GPS units which will accept OSM-sourced data, and I suspect that most of them are Garmin models. I use a Garmin 60CSx (the precursor to the 62ST) along with maps generated from OSM by the folk at
http://openmtbmap.org/