Thanks for the input jramauri, much appreciated
The work is for replacement unit models in the realtime strategy game Rome:Total War. Some screenshots are at:
https://www.totalwar.com/community/rogal3.htm (cycle through the gallery).
There are 4 levels of detail in the models from low poly (150ish) up to high poly (600+ ish). I'll be concentrating on models and textures for the medium/high poly models but am finding it a good exercise to try and do the low poly modelling too.

That link should be very helpful (cant see it at work) if it goes through each of the parts of walking. I really should have IK rigged the arms/legs for easy control and put some controls for the roll of the body/hips etc. I think I'll have a go at those and then as you mentioned try and add the weight into his step. I need to make the upper body more flexible too and swing the arms a little more.