So we've found a way to properly measure the lag, i.e. how much the server freezes. We have found that US Adv East suffers significantly worse than the others, with hiccups of about 1-3 seconds. For comparion, any hiccups on the other servers are generally 0.2-0.3 seconds and much rarer.
Given that we have now established identical 'containers' the Tempus runs in, this most likely means the issue is related to the host. Potentially performance of the hardware or resource sharing. Weird thing is all four US servers use the same host, so we'd expect same performance there.
Either way we're trying our best to figure out what's going on here, and will move host if we have to. Apologies for what is a pretty poor online experience for the US guys atm.