It sounds like you're more concerned with simulating locomotion (e.g., stuff like interaction with the world and the physics/mechanics of movement) rather than navigation (e.g., path finding type stuff). Terminology confusion aside, I had posted the following link in another recent thread. You may find it useful. The implementation is, as I recall, on top of Unity3D. But there's enough technical ideas in there that it may be useful to you. I think it could be adapted to quadrupeds:

Automated Semi-Procedural Animation for Character Locomotion

That technique isn't super easy to implement, but it is kind of nice for realistic locomotion. There are some fairly easy ways to implement robust locomotion in small footprint code, if you can compromise, e.g., if you could ignore foot placement and skeleton/bone-level collision avoidance, then you can do some really simple things like use a swept sphere or even a line to avoid collisions in the desired movement direction, and just ray trace down onto the level/terrain geometry to decide what the height will be...ray tracing from above the character's current height by the amount of maximum step or jump to deal with navigable obstacles while avoiding big things like large walls. This sort of approach doesn't give you pristine, never-a-collision and never-an-interpenetration result, but it can be done in small code, is pretty easy to implement, and can be super fast.