I love your question! Well, I really like the no shoes policy. (I have to mop the floor continuously because I live in a dusty area though, but it is totally worth it)
1. Set the narrative:
You are definitely gonna have to go for the strong and memorable strategy, but make it fun and amicable.
Be explicit and official about it:
Organize a party and add the "no-shoe" term in the title of the invitation, make it sort of the main theme. Because you are not asking for a favor, this is official.
You are invited to my No-shoe movie night (party, drunk night, sleepover, whatevsies)
People remember the purpose of a space, the invitation is communicating something about your lifestyle making it sound more fun instead of clean.
Timing is more important that message structure.
Even some sloppy phrase like:
All right, finally home! Everybody, shoes off please
Would actually work if you say it when you arrive home with your friends at the moment the door is unlocked and being opened, not before opening the door and not after opening the door, but at the same time the new space to transition into is being revealed.
This particular timing will make your audience link your words with the time and space they're expected to modify their behavior, you are adjusting their mindsets just little bit, a significant enough little bit.
2. Set the stage
Remember that very few people are used to this so we are the ones going against culture and common sense, but that's OK, there's definitely a way to make people understand and remember. The shoe basket is a nice start but you need to make it 3dimensional to have better results.
Why?
Our minds set our behavior very much based on the place we are navigating, architects know this, in fact, that whole profession is pretty much based on this concept, the experience of the space. Even atheist people behave in a certain manner when visiting a catholic temple as tourists, and people who are usually very territorial about their personal space dare to surround themselves with a bunch of strangers at a dance floor on a night club.
So, play with spatial cues
Redecorating the entrance could look fantastic and also help you convey the message.
But I'm afraid you are gonna have to do something that looks ugly at first and keep it there for a while until people get used to it, trace a clear rounded or squared line on the floor that marks a noticeable frontier/border from side to side where shoes are allowed for them to remove them.
Although the recommended washable slippers are a great option... if you want to enforce the rule/policy maintaining a positive vibe, you can provide personal slippers as a gift for each one of your most regular visitor friends, even adding their name to the pair of footwear. No one else can use them and the slippers remain home unless your friend gets very enthusiastic and wants to carry your gift everywhere in their backpacks (it could happen).
Also for not frequent visitors (not regular friends) who happen to be germophobic/mysophobic, they would prefer seeing a basket of thick socks they can put on instead of slippers (that after a while will start to look worn out and shady), the socks basket needs to have a note that say "freshly cleaned" or look extremely tidy without the note
Add a place to sit next to the line delimiting the shoes-allowed area, so they can sit and go about the business of taking shoes off, putting slippers or socks on or whatever.
Reinforce your message since before anyone enters your home, make it as friendly as possible.
Cue repetition is important to avoid verbal intervention.
You will also need to be amicably and sound sincere while saying something like "I don't care if your feet smell, everyone's feet smell" (you might regret this, but hey, you wanted people to take off their shoes), the disposable shoebag/cover someone recommended is a nice alternative to avoid this, it's also useful for people providing services, like technicians and that type of temporary visitor, police officers too, don't chicken out by authority ^_^
And lastly, I wished this was not necessary to bring but I mention it so you are successful at enforcing your policy, influencing other people's behavior requires commitment on your part too, make sure your place is always extremely, super clean like you said you like having it, and you will succeed.
If it isn't super clean at the moment, you should be upfront about it and say:
Oh, we can use shoes for now, it looks ok but I haven't cleaned thoroughly
This way, your visitor will appreciate it and be more comfortable taking their shoes off on a regular basis because they trust you care about the place being clean.
Other considerations
You might want to suspend your no-shoes policy during times you don't have time to clean or can't hire someone to do it.
There was a friend that shared my no-shoes policy but she had a hard time keeping it clean because she had just had her first child and she has cats, getting surprise gunk or invisible sticky goo on one foot or sock is extremely disgusting, the person encountering this situation won't be able to put their shoes on because that will infect them on the inside where it's marginally possible to clean and they might or might not tell you about it, but they will definitely not feel safe walking barefoot or on socks in your house ever again.
Keep all areas where someone might want to take their shoes on/off clean, including the garage.
On a side note:
You might want to mop the floor every time you have people visiting anyways, because you don't really know how healthy are everyone's feet, I'll defend that by saying I'm not germophobe but rather germoaware because I used to have problems with my feet when sharing shower and shoes with my brothers while growing up, I hated it. People who love having our feet perfect tend to obsess about it and obsess about and enjoy their partners' feet too, but beyond that, you can't control, choose or enforce everyone's feet health habits. Second guessing the health of stranger's feet conditions and health can disturb a stomach. If more people knew having healthy feet is not that hard at all, things would be easier for you. People who don't want to take their shoes off might be aware they have an infection, don't make them feel so awkward, street dust at sunny cities are germ free, you might prefer the dust. Well you will have the shoe bags/covers for that situation.
Best of luck.