Thanks for the awesome input guys!
@Christian, that's a good idea. The problem is that the tracker is on another scale, it operates tile by tile, while the feet are pixel by pixel. Also the lizard knows where it is going most of the time (forward) but in some scenarios such as turning around the prediction turns out wrong - it can try to predict, but it can't see the future!
@Gimym JIMBERT, as always, thanks a thousand times for the interesting resources!
@Lee, wow! That's awesome! Actually what you describe seems rather close to what I have, except that you describe some kind of "overmind" controlling all the four limbs, making sure that they move cross-wise etc. In my solution the limbs are more autonomous, which has good parts and bad parts. The good part is that they are less static - they don't need permisson to move, making the movement less of an "animation" and more intelligent. The bad part is that they're not intelligent, and I end up with stupid bugs. I actually implemented something similar to your solution, but instead of placing it in a coordinator object I connected the feet into pairs and enabled them to know some stuff about their partner, changing their behavior depending on what the partner is up to.
Update 300Ok, so I haven't really had a huge break through, but I've moved forward through blood sweat and tears instead. The new solution has many little mechanics in it, but the core difference is this: The
first time a limb tries to find a reach position, it reaches too far in front of itself, to where it expects the body to be in the next couple of frames. If the body does catch up and the position actually becomes reachable, all is good, it goes there and grabs the terrain.
If the lizard changes direction or some other weirdness however, so the target never becomes reachable, a counter starts to tick. Every frame that the reach target is outside of the limb's reach this counter increases. When it reaches a certain number (I used 15 frames) the limb decides that OK, this target is probably not going to be within reach, ever. It then tries to find a new target, this time playing it super safe, only going for terrain that is strictly within reach.
On top of this other systems are implemented to smoothen the walk cycle. One such is that if every limb is grabbing terrain, the one that has been doing so the longest will automatically let go and go find a new target. This keeps all four limbs from syncing up in the same cycle of grabbing and moving.
Another one is that the front limbs and hind limbs are connected into pairs. Or rather, one of them is aware of the other. The one hind leg that knows about the other hind leg will try to be at the opposite of the other's cycle, and the same for the front legs.
Slow motion of pink lizard moving (and looking up, I have my mouse pointer up there):

The steps are longer, and the movement is smoother. There are still problems in more complex terrain though, but I feel this is a good start.
For the green lizard I don't want the movement to be smooth, and have allowed the limbs to sync up:

I'm still not entirely happy with it though. The legs should move at the same time, but not sync up so perfectly. I'll look into making them have just slightly different grabbing targets. Also the foot should obviously not move above the hip making the leg turn like a wheel.
The blue lizard takes smaller steps. It looks kind of strange now because the limbs are as big as those of the others - that'll become more proportional once I get the movement down.

In 2D terrain that isn't just a flat floor many of the problems become evident. The limbs have a bit of flailing, and some hesitation when they try to reach for terrain but fail and change their minds. For these specific climbing scenarios the limb movement actually looked better before I made the changes, so I'm contemplating making some kind of differentiation between floor crawling and climbing and using different systems for limb movement depending on the situation.
Hahaha and also, I've finally encountered the backside of inheritance! All this messing around with the limb code has somehow made the poor slugcat's arms disappear! Don't worry though, all the code I wrote is intact, so getting them back again will probably be a quick fix

Getting there!
Another thing!Monday I'm going to do some serious relocating of myself to way over in Seoul! The idea is that I should get to work as quickly as possible, but there will probably be a lack of updates at the beginning of next week. Travelling will take something like a day and a half in itself, then comes being jetlagged, re-adjusting, finding somewhere to sit and work, etc etc. But by the end of next week I hope to be back in business!
안녕히가세요!