did a quick edit to show what we mean by the legs being too wide, while also utilizing what you've already done to add a bit of depth to the steps.
Edit: might be worth tweaking this idea though, as currently he looks like he's doing the Jive Strut haha
I really like how both arms move when he's walking I am going to try to execute something similar but for now I have the East side view walking animation and would love some feed back to let me know if I am going in the right direction..?
Don't like it one bit in my opinion but that's the best I have been able to come up with.
EDIT: I actually changed the second frame a little and I think it looks a bit more fluid now? the arms swing to much compared to the leg but how does this look in comparison ?