If your walk is a 1-2-3-4 (4/4) and you only step on beats 1 and 3, that means you are playing(stepping on) halves,but the time signature is still 4/4.
I think it's note values/durations you don't understand.
If you walk on every step (1-2-3-4), then you would play quarters.
A 4/4 walk has 4 quarter notes if you step on every step. That means you'll be able to step 4 times in a bar. But if you step only in beats 1 and 3, the duration of the whole bar would still be the same. For instance, if the bar duration was 20 seconds when you stepped on all of 1-2-3-4, then when you step on 1 and 3, the bar duration will still be 20 seconds. The difference is that when you play quarters, the notes will last 5 seconds each, while when you play halves, the notes will last 10 seconds each.
This is your walk if you step every single step:
And this is if you step on steps 1 and 3:
As you see, the 4/4 is the same in both situations. It's just the note duration that change.
In the first example the note durations are shorter, whist in the second one are longer. That's the point of the note values/durations.
Here are some links that might help you:
Note Durations on Piano
Learn Duration of Music Notes with Soft Mozart
Another video with Note Durations on Piano
And some charts that will help you :