So today I figured out which servo is on which leg, rebuilt the legs to make the coxas longer, trimmed all servos again, added pieces of rubber tube as feet, and replaced the battery with a larger one.

I also adjusted the voltage to be exactly 5V (it was 5.2V for some reason), hopefully that will make this thing heat less.

Finally, I made some small fixes and adjustment to the code, and lo and behold, we have a walking robot!

It's still not perfect, of course, but at last it works.