Abdul Hadi Pasha said:
Meh (to coin a phrase), Frederick wouldn't have had any more luck running a Kingdom of Jerusalem than anyone else. This was a diplomatic triumph, but a fairly insubstantial one. It lasted something like three years. Ask the residents of Cyprus and Crete how much they appreciated Italian rule, BTW.
The Normans (and then the Houenstaufen) had quite a good record in handling subjects with a different religion in Sicily and Southern Italy: effectively, the Southern kingdom was organised on a very sound and centralised basis, both from the taxation point of view and the recourse to law. The real troubles there started later, after the death of Frederik II (and a good portion of them stemmed out from the fact that the kingdom was a feudal subject to the Pope).
Strnge to say, also the other Norman fiefdom in Outremer (Antioch, under the Altavillas) was generally governed in a reasonable way.
The problems you mention (Crete and Cyprus) were mostly arising out of the Orthodox populace resenting their Catholic overlords. OTOH, Venerian domination in Crete lasted four and half centuries; Cyprus was for 3 centuries under Frankish and later Venetian overlords. The Ionian Islands were Venetian from the 15th century up to the French Revolution. In all cases, it took a foreign conqueror to change the status quo.
A true Imperial Domination (like it might have stemmed out of the Houenstaufen House in another TL) would certainly improve the conditions of the local populace: empires are not much interested in changing the beliefs of subjects: they want peaceful domains and taxes flowing. The idea of an empire spanning Egypt, Cyprus, Crete, maybe Tunis would not be so unlikely.