Servus!
Ich war schon einmal auf Menorca zum Urlauben, allerdings bin ich zu dieser Zeit noch kein MTB gefahren.
Prinzipiell schätze ich die Möglichkeiten aber eher gering ein. Es gibt nur einen Berg. Ist natürlich möglich, dass von diesem ein paar schöne Abfahrten runter gehen, weiß ich aber nicht.
Prinzipiell darfst du auch jeden Weg dort fahren, musst aber wie in den Alpen halt auch, die Zäune nach der Durchfahrt wieder schließen. Diese Wege haben aber eher Feldweg- und nicht Singletrailcharakter und sind der Topographie entsprechend auch sehr eben.
An der Küste entlang gibt es teilweise noch ganz nette Wanderwegchen. Wenn ich mich richtig erinnere könnte da das Biken schon ein bißchen Spaß machen. Sind saubere Singletrails, allerdings eben auch ohne Gefälle.
Zum Thema Bikeverleih kann ich dir leider gar nix sagen, glaube aber ehrlich gesagt nicht, dass du auf der Insel was Gescheites bekommst.
Trotz allem viel Spaß im Urlaub.