What a pain this is! For my FPS, I originally planned to have all control processed on the server to keep things simple: if the user pressed a key on the client, that would get sent to the server, the server would process it and send back a command to the client to say "the unit you control has moved forwards".
In practise, even though the delay was a fraction of a second, it seemed like a lifetime, and movement was incredibly sluggish, as most people who've tried to write an FPS can probably attest to. Instead now, I've had to give the client details of all the map and all the other objects it could collide into, and get it to do the movement processing itself.
Now, when the player presses a key, the client checks for collisions before sending a command back to the server saying "this object has now moved forwards - tell all the other clients please". It works a lot better and movement is now brisk, but it's a lot more complex and involved since I have to do collision detection on the server AND the clients, and make sure they are all in sync.