And thanks for the compliments, Yo-Yo-Master. glad you like it.
Your mushroom looks much better. You could eliminate some of those blues and try some dithering.
I'd say you should consider what you're going to do with those sprites (is it just a mockup or a game running on some hardware) and if its for a game, what will be the capabilities of the hardware. On many devices, it is possible to change the color of the background synchronously with the start of a new line, meaning that with only one entry in the palette, you can actually have a colorful raster for your scene ... and going with dithering actually make the things more complex.
Thats a good point- you obviously know more about the hardware aspect of it. I guess i assumed it was just for fun and not going in an actual game. So really i agree with you.
BTW, Yo-Yo-Master, the sky gets lighter as it goes towards the horizon. It does depend on the time of day but in the afternoon i believe it gets light towards horizon. And, if this is for an actual game you plan on selling or just giving out, i'd love to help.

i can program and make music as well as pixel. And i really love the new run animations! no critique really- they look perfect to me.
[EDIT]
About the head turn. I think your main problem is its too exaggerated. try a 2px head turn, that might work. And i would make the M on his hat 2px long, but thats just me. Great so far!