I am in the same position you are. I considered DreamHost, SliceHost, and few others and went in for a barebone Linux Xen virtualization hoting at vpsfarm.com. Good enough for me to boot up. Why I didn't go for Amazon - though I think EC2 provides way more value for what I am trying to do. BUT - their pricing is very confusing and sucks - while companies like slicehost/engineyard give upfront pricing, and they are scalable too (may not be upto EC2 level). For me, the price plays a big role as we are bootstrapping from our own pocket. EC2 pricing is a huge matrix of upstream, downstream, storage, bunch of other things, which makes it almost impossible to estimate how much you might have to pay! Having said that, I may consider them at a later point of time, where we grow (hopefully) to bigger infrastructure.