Throwing this out there... Bmwsu said in chat that Interserver is now actually using DigitalOcean, which has VPS instead of many different instances running on the same server which causes lag.
https://www.digitalocean.com/pricing/Their pricing seems comparable to our current server if we look at the RAM, but I don't actually know how much bandwidth we're using or about the other things. It doesn't look like it has a Minecraft server control panel either but has a control panel that's more general for pretty much anything, so it might make it harder to manage the server.
I'd probably stick with the brick upgrade for a year and see how it goes.