Bill Caddick used to use a portugese guitarra on 'King Sun, Queen Moon, Prince Night. The late Paddy Doody from Merseyside turned me onto Portugese music, having spent many great hols there, but never heard any music. I have'nt had the chance to go back since.
Other bands apart from Terre a Terra to look out for are, Brigada Victor Jara, Pirates de Silenceo, Uxia, Ne' Landeires and the wonderfull Julio Pereira.(some of these letters should have a funny thingy over them but I don't know how to do it on a keyboard).
I don't know which part of the Algarve you are going to, but my favorite area is the unspoilt western end. We usually stay at a little village called Salema and the waiter at the 'Atlantico',is a Briganda Victor Jara fan. You should find a music shop in Lagos.
Have a geat time
Les