If you need backups by the company themselves that can be used to deploy more instances I would go with slicehost, otherwise linode. Slicehost has more features like a handy iphone app, but linode is cheaper and at least in my limited testing, performs better.