Your motor is operating in two regimes: MOVE_LEG_UP and MOVE_LEG_DOWN. The simplest way of dealing with this is to just know which function you're in, and adjust the gains accordingly. This is a (very crude) version of sliding mode control.
Keep in mind one thing with this approach: the switch is NOT dependent on the sign of the error. What I mean by this is if you overshoot while trying to move up, then the leg has to come down. *but you are still in the GO_UP mode, so keep your gains high*. If you don't, then your robot will "chatter": you'll overshoot just a bit, then the gains will jack right up, you'll undershoot, gains go low, overshoot...
It's not a big deal, but it can be funny to watch.
On the other hand, adding a very simple force sensor will just about solve the problem entirely, but will make position control a bit harder.