It wont be too bad: All that has to be sent is the change in state, so the calculations on position can be amended on each side during a synchronised timestep.
ie if someones holding the left key for 10 seconds, all it has to send is when he presses the key, and when he releases it. It only has to send that as a state of movement, ie: either send 'still','n','s','w','e','nw','ne','sw','se'.
If someone on the other side is moving really slowly on their system (if the games not using delta time), they would appear to move slower, but it would have no effect on your side.