This will only focus on the main character today - tomorrow (hopefully) i'll get into color theory dealing with your background.

so without further ado....

Well, first things first.  Lets talk anatomy.  Now i know that the style you were going for was cartoony, and thats fine.  But since i dont know how intensionally you did everything, I will show you the hard-core correct way, then you can vary off that path as much as you choose to.  In my version i've fixed the following; the head was too big, legs too stubby, pectorial muscels too saggy, you locked all of your limbs so i gave them a little bend, gave him a prince/knight like posture, and a few other minor things.  I'm sure that you catch on pretty quick, so i'm not going to spend any more time dealing with anatomy.  (PS i was just too lazy to draw that crazy hair due you have on that guy)

Alright - now lets talk artsy.  The first thing i noticed about your sprite is the retona burning amount of saturation...almost %100 saturation i think.  Generally speaking, things aren't ever that high in saturation except for controlled situations.  The basic color theory about game design goes as follows; background = low contrast, low saturation.... sprites = high contrast, high saturation.  I'll talk more about that later, but basically its just to make sure the user can always know the difference between his sprite and everything else cluttered around the screen without losing him constantly.  Now although i say sprites are supposed to have high saturation doesn't mean that it can be retna burning and still be okay.  Just lower the hue to be a bit more grey and you'll be fine.  In my version i raised the contrast, lowered the saturation a tad, and added an outline.

The second thing I noticed was your whomping 42 color count.  Thats just crazy.  I lowered the color count to 12 colors plus transparency.  if you notice, even though i have about a fourth the amount of colors you have- mine looks more detailed and shaded.  If you smart with colors, you can achieve this without too much hassle.  Also it makes replacing colors if you need to not nearly as hard.

the last thing that i did to make your character pop out from the background was add an outline.  if you look closely at the outline, its not a continuous black line.  In some areas where light would be hitting, i used a technique called "selout" or "selective outlining".  Learn about it here and any other pixel term you dont understand: (Selective Outlining)  As you can see - sometimes on different colored backgrounds (like you might find throughout various levels in a game) makes it hard to see the sprite distinctly unless it has an outline.  The outline is optional, and not all games use it, but i think you can benifit from it in your case.

Also notice how before i shaded the sprite, i 'blobbed' things in roughly.  This is how i will be animating the whole sprite.  Its generally not a good idea to animate a fully shaded sprite this complex - so instead, you do all of the frames in a simple manner and then shade each one individually.  this will make your animation look more fluid and non-mechanical.  This leads us to our next section - animation.

here we have alot of useful information.  Basically there are 3 steps in creating animation cycles. in step 1 you create base frames; or in this case - the 4 generic running poses that we all know.  In step 2 you create the 'tween' frames; or all of the ocward stuff the body does while moving from one generic pose to another.  In the last step you shade it.  I didn't complete step 3, but you'll get the idea.

Usually people get overwhelmed on the mechanics of how a run animation works, but in reality you dont need to know much.  Just by laying out the basic building blocks of base frames, all we have to do is look at the base frames before and after a tween in order to create a good seemless motion.  Alot of useful info is typed up in the pic itself, so i'll just let it do the talking.

Here is what my step 1 looked like when i was done with it, along with my step 2. 

Its amazing to note the big difference it makes when you add the tween frames in.  Through the tweens opens the door to adding so much character and even emotion into the animation of your run to help 'define' who the character is.

in closing, here is a final comparison to see how much difference these techniques have made in the overall product.  Might be useful for ya.

One last thing i'd like to say before i go to bed is just a quick thing about what defines a walk vs a run.  In games its much better to have the character always running because it makes the game feel more fast-pased and dramatic.  But what defines a walk vs run.  Certainly a run is NOT a sped up verson of a walk, right?  Heres a quick answer for you; When you walk, there is always at least 1 foot planted on the ground.  When you run, there are moments when both feet aren't even in contact with the ground.  Study the animation i made to see more clearly what i mean.

general info about animating moving things:
the first instinct of an amateur animator is just to copy+paste+move and occationally rotate 90 degrees. And the first instinct of a more advanced amateur is to copy+paste+move and edit a little here and there. This is an alright technique to use, but only under certain conditions. If the part your animating rotates at all (Like the arms do), your better off redrawing it instead of the copy+paste method. But if it moves in a different way, its okay to copy+paste+move+edit+touchup. for example. In the animation i posted above, I completely shaded the torso. I did not redraw the torso for each frame. Instead, i just squished and expanded horrizontally a copy+pasted torso to give the effect that it is twisting on the y axis. Even the base torso to begin with (seen in the first pic i posted) was a copy+pasted verson of the profile view i drew. I just edited it to appear as if it has been seen on the 3/4 view. and the shoulder pad was also just copy+paste+moved (and also flipped horrizontally on the forward stroke of the arm). But as i said - in order to have a flowy animation, all rotating parts should be redrawn each time.

Something that i should have also included in my animation was to have the character leaning into the run a little bit to keep him balanced. Also little things could have been added to even further progress the animation. things such as the shoulder pads could have bobbed up and down in due to his bodies rise and fall.

I have already started on the second half of my little critique session and i hope to have it up by tomorrow.  I hope this was helpful to you in some way shape or form.