As I see it, there's a continuum with shared web hosting on one extreme, an private servers at the other. In between there are VPS and 'cloud severs'.
For RackspaceCloud and slicehost, the main novelty over a traditional VPS is that you don't have to deal with some hosting employee to add more servers, or more capacity to a server; you simply go to their website and do the change yourself, or use their API and make your programs ask for more/less capacity.
That's all. management simplification by giving you the keys to the service.
For other providers (Google's AppEngine, for example), the service is more abstract and limited. they only allow specific kinds of software (python and JVM for GAE), so they can measure utilization and allocate more resources. Since you don't get to manage the system, they can seamlessly and dynamically allocate resources in and out. Totally different service and different usage.
Another service typically associated with the 'cloud' buzzword is that of 'infinite' storage charged by usage. Most offer some kind of files behind a web-based API. S3, Mosso Files (now RackspaceCloud Files) are the best know of these. GoGrid offers a similar sevice, but includes rsync and samba access to them, making it a lot easier to use.
RackspaceCloud has one other service, they call 'cloud sites', that sounds a little like GAE; but I don't understand the details of it.