R no está en toda la península, sólo en Galicia. Telecable lo mismo, sólo en Asturias. Euskaltel lo mismo, sólo en el Páis Vasco... etc. etc. etc.
Sería bueno si pudieras concretarnos un poco más en qué zona de Mallorca es donde estás buscando un buen acceso a Internet. Si quieres, haz una cosa: Búscame en GoogleMaps (o donde sea) cualquier negocio/tienda/comercio/loquesea y me pasas sus datos, para ver mejor qué posibilidades tienes, si tienes cobertura con Ono, dónde está tu central DSL, etc. etc. etc.