I know there were a few separate Norman realms but it seems like, especially in the Mediterranean, there couldn't be enough settlers to take control of Italy and Antioch and continue to fight Byzantines and Muslims.
Plus a lot of their conquering armies were pretty small.
So did they ally with anybody else or incorporate people who were not immigrants from northern France?
Was their great power and wide territories ruled, but lower population, a reason for Norman tolerance in Italy?
Sicily is a complex question.
The first key thing to be aware of is that this wasn't Norman expansion. Unlike the Norman conquest of England, Sicily/Italy weren't actions of the Duke of Normandy. It was nothing official. For the sake of saving time I'm going to paste in part of a post I made in another topic:
The impoverished minor noble family of de Hauteville in Normandy was in some pretty dire straits (see The Deeds of Count Roger of Calabria and Sicily and of Duke Robert Guiscard his Brother by Geoffrey Malaterra) so some of the sons (and presumably an assortment of retainers, allies, kinsmen etc) left to seek their fortune in southern Europe. Some of them (the ones mentioned by name are William Iron-Arm and his brother Drogo) fell in with the mercenaries employed by the Byzantine empire who were attacking Arabic Sicily.
Over time, the Normans who had originally come to the south as mercenaries set up their own communities, encouraging more and more people from back home to come down and join them in the battles (see The Deeds of Robert Guiscard by William of Apulia). Aversa in southern Italy stands out as a heavily Norman-populated city that started off as basically a mercenary encampment (see City and Community in Norman Italy by Paul Oldfield).
Having thus set themselves up in southern Italy, the Hautevilles and their associates sought to consolidate their position by snagging more territory in the area. Sicily was largely under Islamic control at that point, which provided a religious justfication, but it seems to have been basically for material gain. Having overthrown the splintered ruling factions of Arabic Sicily, Roger de Hauteville was established as Count of Sicily under the auspices of his brother Robert Guiscard's mainland Italian ducal regime, and the foundations were laid for the later Kingdom of Sicily under the Normans.
Secondly, although not an official Norman action, there certain Norman tendencies visible in Sicily that are relevant here. In a sense, the Normans generally didn't 'conquer'. Instead they tended to integrate into whichever culture they 'conquered'. In Normandy they became quite French; in England they adopted a lot of Anglo-Saxon administrative practices; in Sicily, too, they slotted right in. Sicily was mainly a mixture of Greek (remaining from the Byzantine occupation 400 years earlier) and Arabic (from the more recent occupation by North African states). Although the first wave of Normans there (Guiscard, Roger I, etc) were still very much Normans, the second wave (Roger II, etc) were not so much. There's an article by Mark Hagger (Kinship and Identity in Eleventh-century Normandy: the Case of Hugh de Grandmesnil, c. 1040-1098) that argues the second-generation Italian Normans didn't consider themselves Norman anymore. Roger II, the first King of Sicily, was raised and tutored by a Greek official named Christodoulos and he lived in the primarily Arabic environs of Palermo. There's substantial evidence that Roger II was kind of a hybrid of all three cultures but I won't go into that here. My point is that Normans didn't march in and stamp Normanness all over Sicily and Italy. They integrated.
As an example, the Sicilian Normans maintained the Byzantine practice of recruiting a sort of dedicated notarial class from the lay community (rather than using clergy for notarial duties, as in northern and western Europe). A lot of these notaries were drawn from Greek and Lombard communities in mainland southern Italy, around Salerno and Bari (perhaps the most notable of whom was the chancellor and supposedly secret power behind the throne, Maio of Bari). They also modelled parts of their administration on Fatimid Egypt (see Arabic Administration in Norman Sicily: The Royal Diwan by Jeremy Johns) but that's a huge discussion in itself.
All of which is a long and semi-sourced way of saying the Normans who went to Sicily didn't conquer. They set up a government there but did so mainly by using existing administrative structures. They also integrated culturally, in some cases wearing Greek and Islamic garb interchangeably and arguably speaking vernacular Arabic. Rather than making Sicily Norman, the Normans became Sicilian - and remember, all of this is separate from, and independent of, William the Conqueror's actions in England.