c. 1300, fotman, "soldier who marches and fights on foot," from foot (n.) + man (n.). It also was used in Middle English with a general sense of "an attendant on foot" (late 14c.), and Middle English also had fot-knave "servant of low rank attending a knight or squire" (mid-14c.), fot-folwer "foot-servant" late 14c. fot-mayd (late 15c.) "maidservant, serving woman."
Later it was used specifically of personal attendants to a person of rank who ran before or alongside his master's carriage, ostensibly to keep it from spilling and otherwise assist it on the road, but also to indicate the importance of the occupant.
The non-jogging "man-in-waiting" sense is attested from c. 1700, though the running footmen still were in service mid-18c. Related: Footmanship.
1520s, "footman, running footman, valet," from French laquais "foot soldier, footman, servant" (15c.), a word of unknown origin; perhaps from Old Provençal lacai, from lecai "glutton, covetous," from lecar "to lick." The alternative etymology is that it comes via Old French laquay, from Catalan alacay, from Arabic al-qadi "the judge." Yet another guess traces it through Spanish lacayo, from Italian lacchè, from Modern Greek oulakes, from Turkish ulak "runner, courier." This suits the original sense better, but OED says Italian lacchè is from French. Sense of "servile follower" appeared 1580s. As a political term of abuse it dates from 1939 in communist jargon.