It really depends on what you're trying to achieve.
When you say a few of my web startups do you mean different companies that you manage hosting for or one companies that has several different projects?
Here are the options in order of price:
Shared hosting -- cheapest, but you'll have problems if one of your sites uses a lot of resources. Prices start as low as $5/month (Haven't used this in ages, so prices might be even cheaper)
VPN -- You get a dedicated slice of a host, and you can do whatever you want with it. If you find that you're exceeding the resources of the host, you can upgrade, though it involves some down time. Prices start around
Cloud computing -- I'm familiar with EC2 and gogrid. This is similar to VPNs except that you pay by the hour instead of by the month, and you can deploy and bring down new instances`on the fly. Administration is somewhat more complicated than with a VPN. EC2 prices start at $72/month for a small instance.
My inclination, based on your description, would be to go for a VPN for each startup. That way, if one of them grows, you can just upgrade to the next level VPN.
Slicehost and Linode are two VPN providers that are highly recommended by various people. I've used slicehost and had no issue, though only lightly.