Some of this "shock" must have been over-exaggerated by the writers themselves, because the Byzantines were very familiar with the Normans and others prior to the crusades, both from employing them as mercenaries against the Turks and in their wars with Robert Guiscard. Either that, or there was a sudden technological revolution in the space of a few short years. Part of it may be the audience that they were writing for, who might perhaps not have been familiar with contemporary military matters at all, or else stylistic choices (Anna Komena for example was purposefully writing in a very archaic style, sort of neo-classical, which is why she chooses old terminology for describing the western Europeans).
At Antioch, there was a dearth of cavalry on the crusader side when they sallied out, so it is probably also a good example of their worth as foot soldiers.