Euh.. c'est réellement ce genre de voyage que tu cherches?? Pour ma part je suis allé deux semaines à Madère, en indépendant (tu peux voir mon carnet de voyage ici, et les photos). Il n'y a aucun problème d'organisation.. Entre le français et l'anglais j'ai toujours réussi à me débrouiller.. même avec des chauffeurs de taxi ne parlant que portugais... Et j'ai pu visiter ce que je voulais... incluant Porto Santo.. le tout pour à peu près 2000 euros, sans me priver le moins du monde (repas au resto, hotels 3*, etc). J'ai aussi vu ici, hier ou avant hier, une personne proposant une location à Madère et de l'aide pour s'organiser son voyage.
Pour les hotels l'office du tourisme du Portugal à Paris a une liste utile (c'est la seule info utile qu'ils sont capables de te fournir). Et à Funchal tu peux obtenir les horaires des bus, ou fonctionner avec les taxis (peu chers en général).
Pour info j'avais aussi écrit une ficher technique qui est parue dans le magazine "globe trotter magazine" de mai-juin 2007. Tu peux peut-etre le trouver dans une bibliothèque...