Mario Sprites are BACK!

[Iocus]

I did a quick edit to point out some of the things you ought to look into, but it's basically what Starsock said. Aside from what she said, his face is a little scrunched up and I think you could use a little bit of hue shifting...err, is that too advanced? Basically, hue shifting is when you have a color, like yellow, the darker shades transition into other colors, like, say, red. The spriting dictionary mentions the term as well, if you're interested.

As for the walking animation, are you sure that runs correctly? Usually, people swing their arms when they walk and run. Try looking at some other sprites (Mario or otherwise) for reference.