We've got a GoDaddy dedicated host for $79/month. Bottom of the line model: I believe it's a 1.6GHz Celeron with 1G of RAM or something like that. It's perfect for straightening out the last few deployment issues and seeing if we can get traction before investing a lot in the site, though. We've got full root access to the box.