Aside from my Steve Madden fetish (which, apparently, I share) I have to say, I don’t think this has anything to do with cultural norms or regional expectations or anything like that.
Pure and simple, this boils down to communication.
Everyone here has posted about what they’ve come to expect, what’s customary where they live/within their culture, and what they expect in their own homes. But nobody is talking about how they communicate that to first-time visitors.
Is it rude to expect visitors to take their shoes off? I don’t necessarily think so.
Is it rude to move someone’s shoes? I think so, if you don’t tell them about it.
I do think it’s rude to expect people to read your mind and know if you are a shoes-on or a shoes-off person. It’s even more rude to get your knickers in a twist about it when someone fails to read your mind.
If the hostess in the OP had moved the shoes and then walked up to the OP and said, “Oh, I moved your shoes to be with all the other guests’ shoes. They are over there.” Then I don’t think the OP would have a thread here. What I think the real problem is: the expectations weren’t clearly communicated, so when the OP went to look for his shoes, they weren’t where he left them. This seems awkward at best and rude of the hosts to A) not inform guests of the shoe policy in the home; B) not inform guests where shoes were to be placed and C) not inform the OP that his shoes had been relocated.
I don’t really give a shit if Canadians wear shoes. But I am allergic to unwritten rules and understood expectations. If I walk into your house in Canada, absent other instructions, I am going to march right in there muddy boots and all. If you don’t want me tracking mud in your house, then tell me where you want me to take off my boots and leave them. And then if you’d provide a nice, soft, fluffy pair of slippers for me, I’d appreciate that. My feet get cold. Which is why I wear shoes up north.
When you march into my house in Florida, I do not care if you wear shoes or not. I will warn you, however, that my cat has a leather fetish and if you take them off in my house, you will find a cat rubbing his furry head in your shoes within seconds. If that is a problem for you, better leave your shoes on. Otherwise, I will show you where to put your shoes, if in fact you choose to remove them and if I give a damn where you put them. Typically, I wouldn’t be so rude a hostess as to notice or remark on it one way or the other. Unless I know you have an allergy to cats, in which case I will try to spare you from exposing your shoes to my cat’s cooties. (ETA: I usually remember to ask people who have never been in my house before, “Are you allergic to cats or dogs?” and then will host you accordingly by putting any allergen-triggering critters in another room for the duration of your visit.)
And yes, there is an enormous pile of flip flops just inside my front door. 