In reply to janeho: I can only comment on Mallorca and Sicily from experience. Sicily is (San Vito) brill. You can stay right next to the rocks in a campsite type thing with a pool/shop. The rock we played on was full of friction it was that untouched.
Locals are lovely (as were in Mallorca). San Vito beach is stunning.
The Zingaro trail to secluded beaches is cracking with things to do and see on the walk in.
Big towns nearby (including one on the top of a hill with fun drive up to it (Erice, googlemaps 38.035695,12.590684) and is very picturesque and a tourmap for kids to run round finding attractions.
And no lager louts going to Magaluf on the flight is a big bonus!