You really do not need much. Just a single transition frame will do it for a 5 frame walk cycle.
<img src="http://cyberdog.wikispaces.com/file/view/WalkCycle_Side.jpg/30505746/WalkCycle_Side.jpg" border="0" />
If he is in the up frame (4) You can also have it play the walk cycle backwards until one of the legs is in the passing position, then go to the stand position.. this will make it look just like he put his leg down really quick. All other frames have it play forward, and only stop moving on the passing position frame (the red one in the diagram).
If you want to get really fancy, have a "wait" animation. The first 3 frames have it go from the walking to the wait animation, then have it loop back to frame 3 (pass pos) to loop the wait animation.
WAit animations are usually them standing there breathing, and sometimes looking around or whatever. One of our projects had 1 breathing wait animation it constantly looped, then it would mix in a quick glance up or a hand fidgeting animation then back to the wait loop.
One of the best examples is a game called "Pitfall: Mayan adventure"
They have 4 or 5 wait animations to mix up the breathing.
They made it for Super nintendo, Sega 32x and for Windows 95, and Dos based PC's. You can probably buy it from Good old games (GOG).
Take a peek at the sprite sheets if you get the PC version. You will see all the little tweak animations they mix in. If I am not mistaken the bitmaps are in a Zip file that the extension renamed to .DAT or .PK3. Just open it with 7zip to look at it.
I learned VOLUMES of information from that sprite sheet alone.