Maybe I'm over-thinking it but I think I'd rather just say "Move + " rather than pass in an actual value. This way I think it helps prevent cheating maybe?
Is your player, and all other animate objects in the game only going to move at one speed? Will you not have a speed buff, or a slow debuff for the players? Keep it simple, and use the actual velocities the object is moving at (bullets match this too).
Yes, your clients should also interpolate the other players positions every frame based on the last known information (position and velocity), but your server should still send a full game state every "so often" (how often can be determine based on how frenetic your game will be, how many players there are, how much traffic there already will be, etc.).
This also means you should have time-stamped messages, so clients know, at "this point in time" player X was at Y location, moving at this Z velocity, so you can make sure the player is at the correct state at your clients time.
Good luck, and have fun!