@Erevain: I think you need to work on your lineart (pixel placement), and coloring. I see a lot of jaggies in your character and the tile set. Most evidently the stones. Maybe working at an even smaller scale will help. Some links I gave to UnknownNormals below can probably explain it better than I can.
I remember Turnip Guy
a while back on the forums. Funny to see a similar concept here from a different user. Anyway, yeah, it needs a little work. I do like the grass block, it's simple, but good.
I found myself doing a little edit.
He's a charming character, but might I say his design is a bit weak. I feel like he should be like a Goomba, or other minor enemy/character. Generally for characters, and especially main characters, you really want them to stand out from the rest. Don't let me get you all down though; with the right setting and characterization, he would be fine as the main character of a game. I gave him a happy expression, since he seemed a bit serious. However, the seriousness is fine if you like him that way; I'm just giving some suggestions.
I'm surely no expert, but a few tips I've found useful in my own spriting endeavors...
-Stay away from pure black. It's just generally a good rule of thumb because pure black really weighs a character down, and eats away at detail for the sprite.
-Contrast between tones. The white and gray you have there are not separated enough in tone to really make a noticeable change.
-Colors are a bit icky; but distinct. What I've done is warm up the tones and incorporated some AA with the shading. (I'm still not the best at AAing, just warning) Color theory and anti-aliasing is a whole different topic, so I'll leave you some helpful links instead:http://www.pixel.schlet.net/http://spriters-resource.com/community/showthread.php?tid=13868
-Animation frames don't really change apart from the leaves. For a simple step movement, it looks good, but if the player wants to move more than that, it'll look like he's gliding on the ground. Basically, it's missing the other leg going forward.
-I like that you paid attention to the leaves; it shows you paying attention to detail.
-Parts are separated with different colors so that it's readable.
Welp, that's my two cents. Maybe a quarter. Hope it helps!
@yoshirider4: Nice expressions. Very distinct from one another.
@alex: Pretty sweet. I like the design. I'm awful at dithering though so I can't really offer any criticism there.