Donver, I would say "yes" to all of your other questions.
When I am creating a sprite and I question something about it, I change it until I don't question it. More color and contrast almost always helps. I would say in this case, it most certainly will.
As far as how many frames to use, take a good look at all of your frames. See if each frame is doing a good job of filling in the blanks. Sometimes you may notice that one frame isn't serving as much to the animation as it would if it were changed and perhaps made a little more dramatic.
I've created walking animations with 6 frames that look like they have a lot more frames than your current walking animation does, so I would go through them and make sure that each frame is doing the best job it can. If the answer is yes, and you're still not happy, then add more frames.
Compare your work to some Konami sprites too, just to get an idea.
Good work man, it's coming along nicely!