Server dropping input commands

[Orillion]

We have a fairly large base which is starting to suffer from some lag during multiplayer.
However when I load the map in singleplayer everything is pretty smooth.

The FPS/UPS is at 60/60 which seems normal to me, however the server often does not process commands send to it (like walking input)

When I turn the game speed down it runs a lot smoother and starts processing commands again, but it's super annoying that it drops input commands.

Server is not running any mods.

Server logs only contain user login / logout information which does not seem very interesting or helpful.

The server is running on a CPU with auto-throttling, which sets itself at 1766MHz. When I force the CPU to run at 2666MHz it still does not help much performance wise.
Which makes me wonder if it's actually a CPU issue.

When I run the map locally on my own computer which has a 4GHz CPU it only uses about 25%-30% processing time (on 1 core), however the game runs super smooth.