A few years back I did a day’s mountain biking and a day’s canoeing with this mob:
http://www.algarve-portal.com/en/OBJ/alternativtour/mountain_biking/
The Serra de Monchique area just inland from the Algarve is fantastic. The terrain is hilly without being too mental and the trails are mostly through cork oak and eucalyptus forests so it’s all very lush. It has a bit of a microclimate and is cooler and more pleasant than the coast. One of those areas that has gone on my list of places to buy a bolthole if I ever win the lottery.
From memory the actual bikes themselves were a bit rough but the guiding and the area itself were fine.