Alright, so first, here's a gif of your run for reference.

Leg animation looks pretty alright, although the standing-straight-up middle frame is a bit blah. As far as the body perspective, I find it's best to mix huge movements (which reset the eye - you can be less consistent with your sprite and it'll be okay) and very small slow-in-slow-out movements (moving a segment of the body one pixel over) to get a dynamic feel.
I took a bit to mess with it - keep in mind this is pretty sloppy since I'm doing this when I should be working ;x
Things I changed:
* Added up-down bob
* Offset legs back a pixel to give more an impression of leaning forward
* Torso / Head movement

There's certainly a lot of other ways to approach this- I went for the exaggerated route where you see his back and the arms completely switch positions. My version still has some issues, mind you, but hopefully you get the idea?
