I've had great luck with Softlayer dedicated hosting in the past -- just as good as rackspace dedicated, and about half the cost. The only limitation was not being able to do custom VLANs between servers in multiple cabinets (which I needed for a multicast logging solution). I've never tried their cloud product, though (they should offer discounts to the hackernews affiliated organization...)
Disks seem to be the real weakness of all cloud solutions so far. Local storage is the only cost effective way to have high performance disk, and that makes provisioning cloud instances much harder. There might actually be some stuff to do in this space using dual-ported SAS or SATA with dual port SAS drives, purely for failover.