Are we not making this harder than it needs to be?
For example there are reasons humans have a higher center of mass and it takes more power and effort (and years of practice) to walk: our need to be 5 or 6' tall fluid filled bags for one
Lets take advantage of the clean slate we have with robo waifus. Several stacking advantages could make mobility a non-issue
1. Unfixed center of mass in design: as in "megaman" robots (and the Roll example), center of mass is drawn to the Boots, which themselves could be weighted further. (for "intimate" times the boots could be taken off to reveal more human-like feet, when sitting comfortably or lying down, etc). The rest of the structure doesn't need much, we don't need steel I beams for a skeleton, and the power battery and heavier parts could be set lower on the frame for the purpose of lowering the center of mass.
2. Gyroscopes: as in the Cube example above, gyros provide stability via angular momentum which could even be used to "push" against to maintain balance. Not sure how power consumptive gyros are but I imagine once they are set spinning it doesn't take a whole lot more to maintain the momentum with decent bearings and lubrication.
3. AI assisted learning. Same as how we learned to walk. Trial and error until a way to tackle moving from any point A to B across any slope or terrain is simply reflex. (I'd like to talk more about assigning movements to "reflex" CPUs, this is key since obviously we dont go thinking about every specific movement we need to make, we just think "go down stairs" or "open the door" and our habit and reflex handles the rest, correct?)
Probably more to add to this list, but I see no reason these three advantages would not stack in a way to solve the problem of mobility simply and elegantly.