Linode is pretty good, although you'll have to administer it yourselves. You could also split things up - have the main app on heroku or something, and farm out 'special' (background processing or whatever) jobs to a Linode.