I thought this thread was going to be about some kind of Sex and the City-type culture/stereotype and the popularity of Manolos!
I've travelled and lived fairly widely and I've only encountered a few places where people would even think of entering an establishment barefoot, a few places in developing countries, and one beach party/club town where everyone was basically wasted most of the time. I have seen signs at a beach resort in Israel asking people to put on shoes before entering the shops, though.
I think if there's a cultural difference between the US and other countries at play, it's that in the US signs and visible warnings are very commonplace. I think this is due to the US's legal system. In one of Bill Bryson's books he talks about despairing at seeing signs warning people about things that should be obvious -that it may be dangerous to cross a railroad track without looking, or to touch a pan right after it comes out of the oven, or warnings on packets of peanuts saying may contains nuts, etc. But it's not like Americans are less endowed with common sense than anyone else, that they need to be told that peanuts contain nuts. It's that the US legal system is so much more accessible and democratic than in other countries (which is a good thing), it is easy to file frivolous lawsuits (which is a downside to that good thing). So everything that might potentially be dangerous has to have a warning no matter how obvious, not because they think people won't realise it's dangerous, but so they are legally covered against frivolous lawsuits. I may be wrong but I would guess that may be a factor in no shoes signs - to cover the vendor/company legally if they want to throw someone out for refusing to wear shoes, or if there is some foot fungus infection found.
Another factor is that the US is such a huge melting pot (as previously mentioned) with people coming from all kinds of different backgrounds, and perhaps some people are coming from backgrounds that have different habits where going barefoot is more commonplace.