Your issue I think is the leg movement pattern. If I remember correctly, Spyro moves his legs alternately (lefts legs then right legs). Your animation is good, just try offsetting one side from the other and see if that looks any better.
Think it would help if I offset the legs on our side back a frame? From what I remember, he mostly leaps and gallops while running, but his legs move normally when walking. Youtube doesn't really help as I can't find a good video of him just walking, if they are at any point they usually start charging or jumping. I can't plug in my ps2 right now either, as my only tv takes component rather than composite. :/
but I think offsetting those legs by a frame would work. Is the tail flapping offset correctly?
(Sorry for no image, I'm posting from my phone.)
Spyros movement, if I remember correctly, is quite similar to that of a horse. Try looking up some videos of horses to see how the legs move.