I'd dive into EC2 if you're going to be experimenting. For my purposes it's great to be billed only for your exact usage. Transfers to and from S3 are fast and cheap too.
the problem with the basic 'small' instances is that if there are system problems, you lose your storage. Sure, you can get around this by paying extra for EBS, but it's another problem you need to deal with (and pay for) that is largely taken care of on most VPSs. (which isn't to say you will never have data loss on a VPS, but all the major providers mirror disk, so it should be fairly rare.)