As a startup where would you host stuff? Dreamhost looks the cheapest?

I would not choose solely based on price and if you're looking at a shared server definitely not a place with ambiguous terms of service.

"If your processes are adversely affecting server performance disproportionately DreamHost Web Hosting reserves the right to negotiate additional charges with the Customer and/or the discontinuation of the offending processes."

Before you go with them call them up and if their capacities will work well for what you need to get started and always have a backup plan for scaling up immediately.

I would get a Xen VPS since you get a guaranteed amount of CPU, RAM, disk, and bandwidth as well as full control of the kernel, firewall, software, etc. I've been very happy with http://serveraxis.com as well as http://unixshell.com but definitely do a bit of research first, http://www.webhostingtalk.com/ is a great resource for that.

Dreamhost for early stages + proof of concept. Why? Because 1) they're as cheap as anyone, and 2) they give you more bandwidth than anyone else. For early stages, I think they'll work just fine.

Once you see a growth pattern, though, you'll want to consider VPS or dedicated hosting. VPS should work well if the ISP can guarantee host performance (CPU, disk, etc).

A few options:

- Amazon EC2. This is cool because you only pay for what you use -- your bandwidth is measured and you're charged for what you actually use, not for a fixed limit. For disk space, it uses Amazon S3, where you also pay for what you use. The Xen machine specs are good enough for most of us. And, Amazon just lowered prices on S3 and EC2. Bad news, though: EC2 is still in limited beta. And who knows when they'll be out of that. :-(

- Sun's deal with startups, which was posted here the other day, looks pretty good, especially the Joyant hosting deal @ http://www.joyent.com/partners/sun/sse. Only "problem" is that you're using Solaris. For some people that is not a problem.

- actual VPS hosting: in my cursory search, I think Teknet unmanaged (http://www.tektonic.net/unmanaged.html) looks pretty good, as long as you're technical enough to handle the virtual server yourself. (And you should be.) Their most expensive pkg gives you more disk space than other providers seem to (80G), and more bandwidth (800Gb) -- to me those are big issues. That's for $100/mo, which is a good deal IMHO. Unix-only, CentOS, Fedora Core, Suse, Debian, Ubuntu.

I am currently using Dreamhost right now for a staging server. The reliability has been terrible. I have never seen the uptime go over 24 hours.