Here's another stab with the feet moving more evenly.  I was trying to play around with timing by changing the distances, but I think I was just barking up the wrong tree.  It works much better now.  But I am still a little unsure about how to handle the distance from the last "foot on the floor" position to the most "forward" position.  It feels like that should cover more distance in fewer frames, since you would bring around your leg to catch your body falling much faster, right?

As for the head, I am running into a wall on this one.  Every subpixel anim I try seems to not look quite right to me.  I think I may just be scared to make it move too much, since I want the walk to feel more naturnal and not too exaggerated.  Any more advice?

Thanks again for the crit.

After seeing another post with Scott Pilgrim sprites, I decided to check out the book.  Turns out I'm now an addict as well, so I decided to work on a little game of my own starring...  Knives Chau!!  I haven't done a walk cycle in a long while and wondered if anyone had any suggestions to make it better.  I'm finding it tricky to animate at 64x64, but I really want to keep my resolution and project small.