I also highly recommend studying FF4's sprites, as they are smaller than 20x20, and use only two frames. You can get a great sense for how to portray movement in just two frames without it looking jerky ((for me, the larger a sprite is, the more frames of animation it needs to look good)).
Here's an example of a walkabout from my newest game, which I'm fairly happy with:
Down Frames: I used to try to make things kinda more dramatic-looking in my down frames, like with a big fist way out in front for the forward-arm and more drastic shading, but eventually I realized that unless you're doing at least three frames, that just looks spastic when animated. That's the key here: keep in mind how the animation will look, as being a bit more important than how the individual frames look. The subtler movement here is a lot less jerky, and makes the walkabout feel better, in my opinion.
Side Frames: Again, you have to make a couple compromises to accommodate the two frames of animation. The big one is this: in the frame where the legs are kicked out, SHADE THEM THE SAME WAY! I always used to shade the rear leg darker than the front leg in those frames, because it makes the individual frame look better, but all this accomplishes when it's animated is making the walk cycle look ridiculous, like they keep throwing the same leg out in front over and over. If you shade them equally, the eye will kind of compensate for it, and it'll look a lot more natural, like they're actually using both legs for walking.
Up Frames: Not much to say here that isn't covered in the down frames; I had to restrain the movement considerably to make it look natural.
As an aside, I've also found it's a lot better for walkabouts not to worry too much about directional shading and such; it doesn't add a whole lot at this resolution, and just tends to make it a lot more difficult for you to draw mirrored frames, as you have to redo all the light and shadows as well. Shading them as if they're illuminated from directly above is likely sufficient, lets you put a nice circular shadow under the feet that really anchors the sprite to your tiles, and cuts down on the labor involved in making all your graphical resources.
I also recommend what Charbile said about making a kind of "template" that you can use for 90% of your walkabouts; will save time immensely. And honestly, nothing wrong with having standardized animation for 90% of characters, with the limitations we're working with, it'll just be distracting otherwise; let variety show through in the character designs instead.
EDIT: ((Full disclosure - at least 90% of the "insights" in this post came directly from working with / talking with Shizuma, who is maybe the best person to ask for advice on pixel art, in my opinion!))
SPELLSHARD: THE BLACK CROWN OF HORGOTH now COMPLETE!
Grab it today!