You probably won't be able to get away with 4 frames.
Recently I made a 32x32 side-view sprite, and had to go with 8 frames, it looked too choppy with only 4.
You could try making four leg poses, mirroring and opposing them, and then doing the in-between frames by hand. Am I making sense? I'm not very sure.