I've had my server up for about a year and I've gone through a couple server hosts, but it's just not working out performance-wise. The problem is, I don't know what to look for in terms of CPU power.

Currently I'm with Streamline Servers, and I have their HPGS (4.3-4.5 Ghz) / 16 GB memory plan. It worked well for a while, but it's gone downhill over the past few months (this month being the worst).

Our requirements are more demanding than the average server. We're 'no decay' and average about 30-40 players (50+ on occasion). We usually end the wipe with upwards of 300k entities and 12-14 GB of RAM being used. The CPU is the issue, and it's the one thing I'm really confused about.

What should I be looking for? Most hosts use Intel Xeon. What's the difference between that and i5/i7/etc? What about cores/speed?
Would something like a Vultr '6 CPU' plan work? At $80/mo, that would be the cheaper option, but they don't really list any hard specs, so I'm not sure if it will work. Just don't want to end up with the same issues I'm having now.

Any insight would be greatly appreciated!

Well, to start off - you need to decide, which OS are u planning to use. Windows is overall better for rust server, but it will consume more resources itself. Linux on the other hand will use less resources, but u will likely have some difficulties with setup. 
Not sure about core count, my observations are that more than two cores doesnt make any difference on server performance. Core clock is much more important, so if some host offers 3.9GHz+, consider this option. Ram requirements are 8Gb+, and u should setup a page file with a decent size

Rust server is not multithread for cpu ;) i7 is better than i5 (what u want really? vanilla? modded? how many players? 

Core speed > 4ghz is better

Xeon vs i7/i5 – What’s the difference?

Most commercial VPS servers use Xeon CPUs because they are dealing with multiple server accounts on the same machine, so they need the threads and reliability to deal with that. As Tanki says, it's the core speed that matters to you, that's why your current host offers you 3 tiers of core speed.

I have to disagree with the 'difficult setup for Linux' comment, it's actually very easy indeed if you use LinuxGSM.

I think most of the users on this forum, like myself, run smaller community servers so you may not get any first-hand opinions on high-end hosting plans. Have you considered building your own machine and host yourself? I often see people on here complaining about poor performance on their commercial server and it strikes me that you have no idea what hardware resources you're actually getting, you only have their word for it. If your server is crammed in with 100 others all fighting for CPU and bandwidth there's no way you can know about it. If you're considering paying $80/mo you would soon recoup the upfront costs of your own hardware - you don't need a GPU so that reduces the cost by quite a lot compared to a desktop/gaming PC. Plus you get the perk of playing with 0 ping :) Food for thought.

Well, I'm more familiar with Windows and definitely prefer it, but from what I've read, Linux offers better performance due to the lower overhead. It's also nice to not have to pay more every month for a license. I managed to get a server running in a VM with LinuxGSM, so as long as there are no other downsides to Linux, I'll probably go that route.

If my host is currently giving me 4.3-4.5GHz, is a dedicated server or VPS running at ~4.0Ghz going to hold up better? I imagine a lot of these shared Rust hosts overload their servers, but could it be so significant that having more resources to myself at a lower speed would run better?

Getting my own hardware and colocating would be great at some point, but unfortunately that's probably down the road a bit. Right now I'm just scrambling to get my server moved... somewhere, before I lose all my players. This lag issue came out of nowhere, and I wasn't really prepared for it.

I'm afraid I can't help you with any commercial hosting recommendations, I'm a self-hoster. My gut feeling is that even if you go VPS or dedicated and start paying through the nose for it, you still have to put blind trust into what they're telling you. If you hang around these forums for a while you'll see people post all the time about problems with their hosts. Seems like pot luck to me whether you get a good one or not, and even the good ones can go downhill, as you've seen.

What's your internet upload speed like at home? Rust server requires a surprisingly low amount of bandwidth. I run my own (Linux) server right here under my desk, it's great. I have full control over it, and if it ever has any problem (it never does), I know I can see to it immediately without having to send in support tickets and wait/hope for someone else to deal with the problem. Plus, I know exactly what I'm getting from my hardware.

Going even further with this, for several months my Rust server was installed on my (Linux) desktop PC and it ran fine there as well - I used to play and host on the same machine. I think you could install it on Windows just as easily. You say you're looking for a temporary quick solution, so maybe this could be an option?