[mr_t]

As obvious as it may sound, just buy a pair of barefoot shoes. Go into a store close to you and ask the staff for help choosing the right shoe for you. Definitely get some insoles for the shoes as well (since the sole is usually very thin). This reduces the stress on the sesamoid bones (I think they're called like this) a lot in the beginning.

Then just start walking outside. Watch some youtube videos on how to do it and just experiment and adjust the way you walk all the time (to give you a bit of perspective, occasionally I even play around with my walking style today, 2 years after starting). I tried to see it a bit like a stretching exercise in the beginning. If I felt a stretch of tight muscles (usually calves), I assumed that "I did it correctly"; like in stretching, where you only feel a deep stretch if you do it correctly. But important note: This only worked for me because my calves were indeed tight. If this is not the case for you, this analogy won't work for you.

But most importantly, listen to your body(!) and don't be afraid to look stupid in public (experimenting with your way of walking, while learnign a new way walking, will definitely get noticed by others the beginning; at least that was the case for me).