Rackspace's lowest level machine (http://www.rackspace.com/cloud/public/servers/pricing/) could do the trick. I've personally had one for years (They used to be called slicehost) and I've been mostly happy with it. The lowest one has 512mb of ram though, which you'll maybe scrape by in regards to Moodle 2.3x . I'd suggest you use nginx+fpm because of it's lower memory footprint instead of apache+mod_php. You need to keep your Apache MaxClients low or your php-fpm pm.max_clildren low so as not to use all the memory on such a low memory machine.
You are right, some VPS providers do really oversubscribe their machines.
Have you checked the machine is already overloaded? If you already have root access you should be able to tell fairly easily.