Foot/toe/core strength are all helpful to ones balance. Various foot and core strength exercises alone could be helpful. But balance is a skill that can be practiced separately. Basically this means that you have to find ways to train the neural pathways between your inner ear and all those foot/toe/ankle/core muscles. You might try spending a several minutes a day balancing on one foot at time, while wearing the problem dance shoes, first on a hard floor, and then on a squishy mat. When you get good enough that you get bored doing this, you might also add practicing your latin arm actions, or something, at the same time as you balance on one foot, to add challenge. After a few weeks of doing this, walking might feel much easier.