You can get a 256MB slice with root access for about $11 per month. When you need more, you can scale up to 15.5GB. They have really good support (phone, chat, and email).
Hey thanx for the tip, I did their live chat and their instances come with LAMP already set up and can use webmin/plesk. I've heard good things about them and so far they are living up to their reputation. I would have switched a long time ago but for some reason thought they were a lot more expensive. At the height of our business, we needed 500MB storage and 40 GB transfer per month, which works out to about $19, but only on the heaviest months, so we'll probably save money by switching.