So what exactly is the difference between a Cloud Hosting plan and a Virtual Private Server (VPS) ?

It's a bit tricky because the term "cloud" has been widely over-used, misused and abused by many... However, all serious web-hosting providers will consider the difference like this:

VPS Hosting

A VPS is a virtual machine running on a single dedicated server. That server is shared between a number of VPS virtual machines. It means that a part of the CPU time, a part of the RAM and a part of the disk space are allocated to your VPS. If the server is shut down, all the VPS virtual machines on that server go offline.

Cloud Hosting

With Cloud Hosting, you also have a virtual machine, but it is NOT hosted on a specific single dedicated server. On the contrary, your virtual machine can be spun up on any dedicated server of the hosting company's infrastructure, depending on availability. In case a server goes down, all the virtual machines it was running can be spun up again very quickly on a different server. The disk space may be network storage or it may be replicated to local SSDs when the virtual machine is spun up on a new server.

One particularity of this is that if you need several identical servers with load-balancing in order to handle traffic surges, Cloud hosting can quickly (sometimes almost instantly) spin up extra instances of your servers, as many as you need and as long as you need, then spin them down again when they are no longer used. You generally get billed by the hour for each running instance and you have access to an API for managing your instances.

How do they compare?

Technically, a VPS infrastructure is simpler and easier to set up than a Cloud infrastructure. Therefore VPS hosting will typically be cheaper than Cloud hosting.

However with VPS hosting you may run into limits that will make you prefer Cloud hosting:

• With VPS you can grow the specs of your virtual machine, as long as there is space on your sever (depending on other clients). After this, tech support will need to move your virtual machine to another server with more available resources. This may take days or weeks. Sometimes it's not possible at all. With Cloud the same operation will only take minutes or maybe even seconds, because the infrastructure is built for automatically moving VMs from server to server.
• With VPS, if there is a hardware issue with your server, you get downtime while the server gets serviced. With Cloud, if there is a hardware issue, you get moved to another server and you barely notice the downtime.
• Cloud allows you (via an API) to scale up and down the number of virtual machines you may be running simultaneously. VPS is a reserved slot on a server, with no easy up and down scaling.
• Cloud hosting also typically comes with infrastructure management. This means that all your cloud instances can communicate on a private network that is automatically configured. This is useful for separating your application server from your database server, for database replication, for placing a load balancer in front of your application servers, etc.

Conclusion

• VPS is best suited for small sites that need flexibility (root access) but can run on a single (virtual) machine and/or need to contain their hosting costs.
• Cloud is best suited for sites that rely on a multi-(virtual)-machine infrastructure, typically with load balancing and potentially up/down scaling depending on traffic surges.