The need for people with foreign language skills is the highest in the regions where the majority of foreigners go, thus Baleares, the Canary Islands, and the Mediterranean coast. There will probably be few possibilities on the North Coast because it is not a region for mass tourism of foreigners.
I have heard from a few persons who worked in holiday resorts as entertainers, sport instructors or service staff; the big holiday clubs usually hire persons with foreign language skills. If you know German, you might want to check for example
http://www.robinson-club.de/ron/list_unterrubrik.hts?unterrubrik_id=19 I guess German would be a high asset especially in Mallorca.
If you do not want to live in the tourist regions, but in Madrid, I would think it might be easier for you to find a job teaching English-there is definitely a need of native English teachers and with the Spanish passport you do not have any problems to work there legally.