Roman shoe from a sculpture in the British Museum

The calceus was the formal closed shoe worn with the toga by Roman citizens outside the house; in the house sandals were worn with the tunic. Footwear came in many different styles, and was differentiated by class though not by gender. Slaves went barefoot. Senators and curule magistrates wore high shoes with black laces and an ivory crescent fastening (lunula) or mullei (crimson leather shoes).
Umbricius expresses embarrassment at the visibility of his poverty in the high-maintenance costume clients were expected to wear to the early morning call on their patrons. In Sat. 1.119 Juvenal describes the sportula (dole) as the means by which poorer clients not only ate but maintained their civic uniform: hinc toga, calceus hinc est.

Roman footwear (photo courtesy of VRoma)