Norman armies, when they could, were combined arms affairs. They would have fielded a good mix of cavalry, infantry, and archers (William Iron Arms lopsided all cavalry victory in Italy was not the norm).
William's army consisted of Norman foot and milites, Flemmish foot, and Breton milites (in reality probably also a mix of foot and horse). The Flemmish were famous for their heavy foot by this point, and the Bretons were well known for their mobile cavalry (used more thrown weapons vs the more straight up Norman heavy cav).
Figure something like 3-5 foot per each cav, and archers/crossbows equivalent in number to cavalry. Archers/Crossbows to soften up enemies, before the infantry held the middle/softened up the enemy further. Milites to come in to finish off a weakened foe. That is, in practice, how the Battle of Hastings is described: shoot at the English, hit them with infantry, fall back, hit with cav, fall back, rinse and repeat). In some respects it sounds a bit like the Roman triple line strategy (Hastatii/Princeps/Trirarii, but with different types of troops), and it is what finally did the English in. In the end, after several failed false retreats the English line broke and chased down the hill, letting the milites swing in from the side and start the slaughter.
The 'knights over everything' was a much later, French, thing. The Normans were well feared for their cavalry charge, but with few exceptions, that was a decisive blow not the main act for them.