The requirements are fairly simple, just about any VPS will work... And, you're right. The pricing is crazy. With my webhost (who I love deeply and would recommend to anyone), a VPS with 2 gigs of ram is $70 a month! Crazy!
What I recommend is
Amazon's Lightsail program.
You will need to set up your server under Linux (They have optional Ubuntu images), which is actually pretty simple, but seems to have everything you could want.
Looking at performance on my home ubuntu server, you can easily get away with the $5/mo package during development. That will handle both the server and a CED server running without issue. You can get about 10 players before things get dodgy. Two gigs seems to be the minimum for more players (again, we're trying to run CED with users connected, and ~50 players on the server, and not see hardware related lag), but for $20/mo, that seems pretty reasonable.
Edit: On cores, they help a hilarious amount, so if you have the funds, getting that second core is a wise investment.