Hallo Layla,
Palma wäre ein sehr geeigneter Wohnort für Euch. Nicht Playa de Palma (ok, ginge notfalls noch) oder gar El Arenal, sondern das Zentrum von Palma. Die klassischen Touri - Orte erwachen Ostern meist gerade erst aus dem Winterschlaf und bei den Reisen, die Ihr schon unternommen habt, weiß ich nicht, ob z. B. Santa Ponsa oder Cala Ratjada, wo Ihr lustige Bilder in den Speisekarten und garantiert "deutschen" Filterkaffee an jeder Ecke bekommt, etwas für Euch wäre

Da ist Palma schon etwas authentischer.
Die Busverbindungen auf Mallorca sind eigentlich in Ordnung und vergleichsweise zuverlässig. Ich denke aber auch nicht, daß Ihr mehr als 10 - 15 km pro Tag wandern wollt, insofern dürfte ein notfalls erforderliches Taxi auch nicht allzu teuer werden.