I've been happily using a VPS from http://www.digitalocean.com for my hosting for the past 6 months or so now. Great service at a great price.
Until the recent SQL vulnerability in Drupal was announced on Oct. 15, 2015 I'd been quite pleased with the performance of an Aegir installtion with 1G RAM. But somewhere in that timeframe (most likely unrelated to the SQL vulnerability) I started getting some processes failing due to inadequate memory. Adding a swap file didn't seem to change that, so I've just today upped to a 2G RAM VPS.
Very, very pleased with how th upgrade went. Just take a snapshot, destroy your old Droplet (that's what they call a VPS instance there), and create a new Droplet from the snapshot image. I must say, I was a bit nervous destroying the old droplet, but in a few minutes the new, larger, faster droplet was up and running. Flawless. Plus, digitalocean keeps an image of your recently destroyed Droplet, just in case. I don't know how long they keep that one for, but it's just extra asssurance so far as I can see.
BTW, if you you use this referral code when signing up, you'll save $10 (and I'll get credit too, thx):
Basically, with that credit, you can try them out for a month with a 1G RAM VPS for free. Nice.