1878 – Toy Mechanical Horse – Andrew J. Davis (American)
Patent number: 209468
Filing date: Jul 26, 1878
Issue date: Oct 29, 1878
see pdf here.
Although a patent for a toy, the walking mechanism is what's important here. On the whole, I have found that toys, particularly those that actually made it into production, show proof of concept in most cases, and that future builders can learn from successful, albeit old designs.