My understanding is that shoes are required primarily for safety reasons. An establishment's insurance probably requires them, in order to cover any injuries from broken glass and the like.
A number of years ago, in my province, there was a case where a woman went shirtless around town. She was arrested and fought the charge. It was ruled unconstitutional that she was not allowed to go shirtless, when men were, with no charges. So anyone who wishes to may go topless. The 'No shoes, no shirts, no service' signs predated this incident but it is probably enforced so that everyone is wearing a shirt inside. There was a funny editorial cartoon at the time with an older couple, both topless. The husband looked at his wife and said, 'You're going out like that?!?!?' And when you looked at the two of them, their chests looked pretty much the same. He had the man boobs going on and hers were a little saggy from age. It was hysterical.
Last summer, there was a thing on the news about a woman who hated wearing shoes in the summer. She went barefoot everywhere and was often refused service. So she invented these foot coverings that made it look like she had sandals on but still left the sole of her foot bare. Personally, I thought she was being ridiculous. And if I saw her wearing those things, I'd refuse her service because of the insurance issues.
Children in strollers or babes in arms don't require shoes. But if they're walking on the floor? They need shoes on in most establishments.