Maharal in Gur Aryeh answers that of course Bnei Yisrael had shoes. Rashi means exactly the opposite of how the Mizrachi understood him -- *because* Bnei Yisrael had shoes, their feet did not swell up like would happen to someone walking barefoot.
So if they had clothes and they had shoes, why does the pasuk use two different clauses to tell us that? Why not combine the two into one sentence, e.g. “simlascha v’na’alcha lo balsa…” or something similar?
Maharal says a yesod: the pasuk separates clothes from shoes because clothes are for polish, for kavod, for a person’s image; shoes are a necessity.
When we wake up in the morning and get dressed we say the bracha of “malbish arumim.” When we put on shoes, it’s a differnet bracha: “sh’asah li ko tzorchi.” Shoes are a “tzorech,” a need – not a want.
R’ Yochanan (Shabbos 113a) called his clothes “mechabdusi” – that which gives me kavod. “Clothes make the man.” There is no cliché that says “shoes make the man” because shoes serve a purely functional purpose. Clothes express who you are and what you think of those around you; shoes are just there to protect your feet from blisters (your wife and daughter will undoubtedly argue - I’m just reporting what Maharal says. He obviously never hear of Imelda Marcos.)
This is why we find that when a person comes to a makom kadosh (Moshe by the sneh, entering the har ha’bayis) he must remove his shoes. The need for shoes’ functionality is not something you want to boast about in these contexts. You can’t even walk around on your own two feet without help and you want to come closer to Hashem?
R’ Hartman in his footnotes calls our attention to the Yerushalmi (Shabbos 6:2) that writes that it is not usual for a person to have two pairs of shoes, one for during the week and one for Shabbos. If a person is obligated to have a different suit and a different hat for kavod Shabbos, why should a person not have a second pair of shoes for Shabbos? Based on what we have discussed, the difference is clear: what suit or hat you wear is depends very much of what you want to say about yourself and your social context. Is this a formal occasion or a casual meeting? Are you sitting around with friends or going to a job interview? Wearing shoes is purely a functional matter - it’s not about getting or giving kavod.
My son pointed out to me that how to read this line in the Yerushalmi is actually a machlokes between the Pnei Moshe and Korban HaEidah – here’s a link. R’ Hartman’s pshat fits according to the Korban haEidah, but the Pnei Moshe reads the Yerushalmi as a rhetorical question (b’tmiha) – “Does a person not have two pairs of shoes, one for weekdays and one for Shabbos?!” Whether or not there an inyan of having special Shabbos shoes may depends on which of these two readings is correct.