Några tips:
Långt ut i palmas sydöstra del "Arenal" är bra då har du till gång till platten, kullar och även berg för en längre tur. I Arenal är det gott om billiga hotell. Missa inte tyskstället Megapark för kvällens öl och storbildssport. Nära flygplats är en fördel.
Soller är finsmakarstället. Jättefin kompakt stads-by och tillgång till berg i tre väderstreck. Inte så långt från flygplatsen i Palma. Ingen platt i närområdet.
Pollenca/alcudia är mer familjevänligt. Tillgång till en hel del bra cykel men lite sämre möjlighet att variera som de andra alternativen ovan tycker jag. Långt från flygplats.
Palma city funkar också, speciellt om nån i gänget inte cyklar, men räkna med att få lägga 20 min ut och in genom stan varje dag, och trafiken är som storstadstrafik.
I slutändan funkar hela Mallis. Det mest praktiska för cykel tycker jag Arenal är men det är en smaksak.