Es Caliu is well worth a visit - amazing steak / grill restaurant with a charming garden, on the St Joan Road (about km13.5 if i remember correctly - look out for the windmill.. the bbq ed ox is amazing! (not on the menu!)
most of the beach restaurants on the east of the island (cala mastella, cala boix etc all do decent seafood ..
Amante Restaurant. It is a beach club.
My favorite beach is Salinas and I stay at Malibu Restaurant. The food there is amazing. You rent a lounge and they bring you whatever you want. The service is without peer. Grilled gambas, yummm.
The restaurant at the Hotel Hacienda Na Xanema is really good, but a long drive. (be warned the road up to the hotel is narrow and steep, so your stick shift skills better be good.) That would be a day trip, part of a tour of that side of the island. There are other good places around there too.
Do not go to Paloma. I am sure someone will recommend it.
La Oliva in the old town disappointed last summer.
Others that I have not been to recently that were really good in the past: L'Elephant, Ama Lur, Chiringuito on playa es Cavallet.