What CPU are you running it on and how many cores are being used? Are you also in really large rooms like Techlore and Matrix HQ? Because I think I'm in all of the largest rooms (and a lot of the smaller ones)
I'm running my instance with lots of bridges in a 3-core 4GB server, paying about eight euros a month for it. Synapse runs just fine, but I'll probably switch to the Rust impl when it's done.
If you want to go cheaper and have only 300-400 Mbps of bandwidth, I've heard lots of good things about this provider:
Contabo is great: finally a provider that does not save on mem and disk space. I moved everything to them and I save tons of money. The 400mbps is only for the cheapest as well: you can pay more to get more. Not that most people would need more. Especially for running matrix for a company etc.
Not those two (and I know those are especially large), but we are in many 5-10k rooms, including bridged Freenode rooms which are known to be some of the worst offenders.
Note that many significant improvements have landed very recently, for instance the chain cover stuff which significantly improves handling of rooms with frequent membership changes (such as the aforementioned bridged IRC rooms).
