The way humans walk is exactly the opposite. The toes are at a different angle from the foot (when walking), so that our feet effectively look something like ___/ , with the underscores being the foot and the / being the toes. We then transition from the ___ part of the foot to the / part of the foot and push forward, and land flat footed with the other foot. For whatever speed you are going, there is a proper ratio between landing on the ___ part of the foot and pushing off the / part of the foot, and that's where balance comes from. That is, the faster the acceleration of the fall, the faster you transition from ___ to / .
So in humans, balance comes from the way one step connects to the next step, whereas Dexter appears to be treating each step as a discrete unit, where it has to attain balance at the end of one step before going on to the next step.
If you actually have to balance yourself after each individual step instead of using the next step for balance, the problem seems in some ways to be much harder.
Also, the balance problem is greatly compounded by the small steps Dexter takes. Compare this to doing lunges. When you do a lunge, you basically take a long stride forward and then sink into it, all while keeping your torso perfectly upright. This gives you a much bigger platform for stability. As terrain gets steeper, the way humans walk becomes more like a lunge for this reason.
So my guess is that taking one tiny step and then balancing is the hardest part of this problem, because you have the least tools at your disposal. For example, you can't use the next step to balance you. However, once you can do the last step of the sequence, all the preceding steps working backward from the last one get progressively easier.
I don't know anything about robotics, but as an athlete and sports physiology geek I find the problem interesting.