Remember that 'cloud' is just a buzzword, intentionally undefined to refer to almost any kind of setup. So, you should first separate apples and oranges. Fortunately, some slightly more precise terms are appearing.
First, the big three kind of services:
- Infrastructure as a Service (IaaS)
- Platform as a Service (PaaS)
- Software as a Service (SaaS)
- IaaS is just a VPS with some API and/or web control that lets the client manage the number of instances at will. The billing is done afterwards, according to usage. This is what Amazon ECC, GoGrid, Rackspace 'cloud servers', Slicehost offer.
- PaaS services don't give you a 'machine' (real or virtual), they give you a programmable environment where you can put your code. That's what Google, and (i think) Rackspace 'cloud sites' offer. You could also say that typical shared hosting offerings are a limited form of this.
- SaaS are a specific application giving specific services. The classic examples are hosted applications like email, ERP, CRM, and so on.
A very related offering is storage (Amazon S3, Rackspace 'cloud files', GoGrid cloud storage,etc), and recently databases (Google, amazon), queue managers (Amazon, Google). You could say these are just SaaS; but usually they aren't very useful by themselves, so they're commonly seen (and sold) as part of a platform, to be added to PaaS or IaaS.
Ok, with all these classifications, you can just plan your requirements and check each provider to see which parts are offered, at what prices, and if they're ready to be used, or if need some extra work.
For example, GoGrid's storage can simply be mounted via Samba, or copied by rsync. Traffic between a server instance and the storage isn't metered. That makes it very easy to use. Rackspace files, OTOH, are more like Amazon: you get an API to read/write files, and can optionally make them visible to the world via HTTP, so you can for example, store images or video files directly referred to from your webpages. Traffic is metered, but cost per GB is way lower... you get the idea.