Yes, up by Pollensa is really nice, although I quite like the hustle of Alcudia and C’an Picafort also. My first ever Spanish holiday was to Menorca in 86. Stayed in a place called Son Parc which had a small cove for a beach and really liked that, but quiet for me though. Think it was next to a place called Son Bou.
Yeah, Pollensa and Formentor (spelling?) is lovely.
