Quick glance at DigitalOcean looks AWESOME! Way better than the pricing estimations I was looking at for other hosts.

Thanks all for advising on DigitalOcean, I think I'll go with them :)