Inverse Kinematics won’t help with the walking, but you will need it.
Two things…
The issue is largely balance and since you have no way of shifting balance then you have a limited number of footfall possibilities. I suggest that you try one of the cat like gaits. A cat can place it’s hind foot just behind it’s front foot, when it does that it is like a tripod, with the feet on the other side providing the other two anchor points, the center of gravity remaining inside the triangle. Three legs move forward at the same speed (with ground contact) and the fourth at double speed to set the new advance. This is called ambling.
Secondly… I don’t know what servos you are using but I have found them to need their own corrections between “set” points to smooth the motion. I have found that faster “refresh” rates do not make smoother motions. I don’t have a solution yet, but I have a path to investigate. You can not study this unloaded, the servos must be under load. Flip it over and weight the feet.
I’m working on winter here and have set my robocat aside for now. I’ve been using the DUE instead of the Mega, for both the solar projects and for the robot. It has some quirks but is fast enough that you can run all the floating point with time to spare.