Also, should I have set the movement of the rig before I animated the legs rather than the other way round?
Yes. Don't animate walk cycles 'in place', because:
You'll just get wrong preview.
You still need to provide movement of whole rig at some point, that is hard to do when you start from 'in place'. Opposite is much easier to do.
XSI tools, such as 'deform motion', likes real walk, not 'in place'. If you want to go further, you can easily create your own deform motion system, by using constraints to surface, with nurbs surface as a 'carpet'. There you still need real walk.
If you want to preview real walk, so it's looking like in place, just take one orthographic view, usually it's left/right, link it's camera z position to whatever is equivalent of upper body controller's z position.