Nick...that is a perfect post. My thoughts exactly.
It is very, very true that you should certainly try (and continue) strengthening the surrounding muscles. In terms of the ankle, you need to work the posterior tibialis and the intrinsic muscles of the foot. I generally hate orthotics, superfeet, braces, etc. I think people (and podiatrists) jump to that far too soon.
But having said that, there are plenty of feet and ankles in this world that are far beyond strengthening to fix. Once the ligaments are deficient enough, and the tendons stretched or torn enough, and possibly the arthritis setting in enough, you don't have a choice but to support your feet as best as you can with orthotics, braces, etc. You want to do what you do and many times those assistive devices are the only way you're going to be able to do it safely. We tend to call these "floppy feet."
Be careful...people say they want "arch support," but many times that means a big chunk of something under the arch. But the arch is not a weight bearing surface...your weight goes through your heel, the ball of your foot at your big toe and at your little toe (like a tripod). Many, many things throw this off and that's one reason why getting Internet advice about this stuff is so hard. Every single foot is different...
Anyway, enough of that soap box.
Stuart: the squishy surface can be anything unstable. The more unstable the better (meaning your toes are digging in, your ankle moves all over the place to try to hold you up). Try a couch pillow, cushion, bed pillow, or roll up a bit of a closed cell foam pad (that would be perfect!). Keep making it really, really hard to stand on one leg.