Here are some results of my first day running a full Bitcoin node on
/ULvXbd]DigitalOcean.com. Unfortunately, it is not possible to run a full node on the $20/mo instance, you need the $40/mo 60Gb VM Debian image.
If you use Debian, Why not try linode? They sit on SoftLayer network and latencies are good.
There are many alternatives, but Linode just like DigitalOcean costs about $40/mo for the smallest required VPS for a Bitcoin node. Besides the storage space, everything else is sufficiently large.