Either that or just simply key the start/end points and then adjust distance until the feet don't slide. Or you could look at it mathematically. If the character's stride is 3ft per foot and it can travel at 6ft/sec, then he should be taking two steps every second. Set the grid to Feet and set the end point at the distance you want it to move in a given amount of time.

Ex.
6ft/sec x 6 sec. = 36ft.
Grid = Feet so 36 grid units = 36 feet.

@24fps
Start frame = 0
End Frame = 144