How to choose between web hosting and cloud hosting?

I think you are over-simplifying the types of hosting that you could get. Here they are, what they're good for and what they're not so good for:

Shared Hosting

You are on a server with potentially hundreds of other people. There are pre-defined limits, such as the amount of disk space / databases you can have and the amount of data you can transfer per month. This is the cheapest of them all, sometimes as little as $3 / monthly but beware - as soon as your site starts consuming more than minimal resources you'll be suspended and asked to upgrade.

Additionally, stuff like PHP/SSH/etc are configured in 'paranoid' mode. You might not have access to certain functions and you must depend on your host to install things that you may need (i.e. subversion / mercurial).

This is good for people who want to host a personal or business card type site. An off shoot of this is called reseller hosting, which gives you the ability to create additional hosting accounts for your customers.

Note, this is not PCI/DSS/HIPAA/Etc compliant.

Virtual Dedicated Server

Your site gets its own unique view of a shared server. You can configure your services and software just like you could on a dedicated server, however there are no real resource guarantees. "Bad neighbors" is all it takes to bring your site to a crawl.

I usually recommend this for developers who need a sand box that allows them to configure stuff the way that they want it.

Again, not PCI/DSS/HIPAA/Etc compliant

Virtual Private Server

This is, for all intents and purposes, a dedicated server that comes with a certain amount of guaranteed resources. You'll be the super user, you can do whatever you wish. Depending on the platform, your resources limits may be able to 'burst' on occasion in order to deal with spikes in usage. Unfortunately, this also means that your resources suffer if several neighbors also need to 'burst'.

I recommend going with a Xen provider if you go this route, you will never have less than what you pay for.

I recommend all new sites that anticipate any kind of traffic start out on nothing less than a VPS.

This can be, depending on the type of hypervisor and storage used made PCI/etc compliant.

Fully Dedicated Server

Exactly as it reads, a server that is yours and yours alone. You can rent one monthly, or purchase one and pay for it to be located in a data center. I recommend going with the renting option first, it requires less investment to scale up if needed. When revenue permits, you can always buy your own servers. By that time, you'll have a very firm grasp on the kind of hardware that you need.

I recommend this for start up companies that can afford a few hundred a month on hosting, or anyone that has to adhere to security standards. If you store CC info of any kind, or any kind of medical / health information, you'll really want exclusive access to your own hardware.

Cloud Hosting

I have built several cloud platforms for some large web hosting companies. I am prolific in development around Xen and even I can't tell you in one clear and concise sentence what 'cloud' is supposed to mean when it comes to IAAS (Infrastructure As A Service).

What you are getting with most cloud providers is one or more virtual machines that can be allocated more memory or storage as traffic demands, then go back to the 'idle' setting when traffic subsides. Additionally, some offer the ability to make clones of a single instance and connect them together using a load balancer (usually software based).

The thing to watch out for here is mega bills if your site gets hammered. There are many instances where the algorithm that 'auto scales' you works more in favor of the hosting company and less in favor of your wallet. If you get that kind of hosting, make sure that switch stays glued on manual. In many instances, just turning on a cache is sufficient to meet an increased traffic demand.

Amazon and others have clearly posted that their offerings do not meet the guidelines set out by security standards such as PCI/DSS or federal standards such as HIPAA/HITECH. This isn't so much a caveat of using a hypervisor, its a caveat of using a shared storage network.

In summary:

The kind of hosting you get is really incidental, what matters more is how you plan your network. For instance, you might have static.domain.com using a light weight http server that has the responsibility of serving only images and media, thereby drastically reducing the load on your production server.

Additionally, smart caching of dynamic pages (and/or) the queries that go into making them let you squeeze considerably more out of any platform.

I'd get a few VPS servers, or perhaps a dedicated server and a couple of VPS servers. The other thing I'm adamant about doing is splitting up my DNS, if my domain can't be resolved .. all the caching and fine tuning in the world is not going to help.

Its really hard to say what would be 'best' for you, I'm not sure about the complexity and needs of your project. However, hopefully, the above gives you some insight into the pros and cons, whatever way you decide to go.

That's an interesting and far-ranging question. I'd say the primary difference between "normal" web hosting and making use of a cloud-based service is on-demand (or dynamic) scalability.

A "normal" web hosting service usually provides a certain level of service (cpu cycles, bandwidth, storage space, etc.) for a fixed price per unit of time. You pay that price regardless of how much of the service you actually use. If your needs exceed the service level then you are stuck in most cases.

The idea behind most cloud services is that the service level varies, sometimes wildly, and that you pay for only what you actually use.

Consider Netflix as a use case: I bet the Netflix service level spikes in the evening and nighttime hours on weekdays and most of the time on weekends (in the USA). So their service level needs Friday night at 7pm are vastly different than Tuesday morning at 9:30am. Using a "normal" hosting service, they'd have to pay for "Friday night level" service all the time whereas with a cloud-based solution the amount they pay varies as their service level grows and shrinks on demand.

With cloud hosting you have to watch out for hidden costs. As most cloud hosts charge for usage when you get a heavy burst of traffic you could get hit with a large hosting bill for that period. Most cloud solutions do not have the ability to place a limit on resource used so there isn't usually a way to limit your costs when experiencing bursts of traffic.

Thats the downside.

The upside is that your website will be able to handle those large bursts of traffic which a traditional single shared or dedicate server may not handle as well.