Don't know the game style, but I suspect point & click.

I'm not sure what the effect of this suggestion will be, but since you know your own code best, you'll know what it does..

You told me you know 3 things.
Starting position.
Ending position.
Velocity.

Let's rule out the ending position and replace it with a direction.
Then you have
Starting position.
velocity.
Direction.

You can let the client calculate the movement until it recieves a new packet. This makes the movement smooth, but if the lag remains, the character can suddenly jump to a new set of coordinates when it changes direction.

Packets a client can send to the server are simply the new commands:
Stop (velocity=0), moving.

Recieving packets should be done in a seperate thread, not in the main thread, this tends to remove lots of lag.

I hope I understood the problem and supplied you with a good solution.