So, it seems to be a good decision to use the working gait code from Arduino, and just send high-level commands over the serial to it. At least it gave me a working robot.

Below you can see it exploring my room with its webcam. It's a little dark under the table, and my screen's refresh rate interferes with the camera, but it feels almost like Doom.