I guess it depends a lot on your hardware requirements. I know that godaddy has some pretty economical virtual server plans. I know they get mixed reviews but I have several smaller clients hosted there with very few problems.
My big projects are typical hosted at the client's facilities and I can tell you that most of them are looking at server virtualization. We can take a single server with beefy hardware and install several virtual instances and they work quite well. In fact, users and other developers can't even tell they are running in a virtual instance. I don't know if that's an option for you or not.