Disclosure: I work for Linode.
Speaking objectively, I've heard from several customers that have migrated both from EC2 (as well as to EC2) that say Amazon EC2 is not cut out for hosting Web services. From the cost per resource to the various quirks of their service -- last I heard, you don't get a static IP and if the shard goes away you lose it unless you pay -- EC2 is designed more for utility computing than running a Web site and its associated services. I would recommend EC2 more for these kinds of applications:
- Processing videos and other multimedia.
- Throwaway computing, where nodes are added and removed as demand goes up and down.
- Any service where CPU is the bottleneck.
A VPS is a much better choice for you, as you get root and -- if a company does its VPS service right -- scaling is ridiculous easy. If you plan for scalability from the get go with a load balancing solution, you can add a node with Linode in under a few minutes.
The two front runners in the VPS market are Slicehost and Linode. Each have their advantages and disadvantages. Again speaking objectively, Linode's cost per resource is better than Slicehost's, and Linode offers a few services Slicehost does not. Both have fairly active and helpful communities, and both are reliable services. Here's a comparison of both where Linode was ultimately chosen, and a discussion on Slicehost's forums with customers taking both sides.
I'm happy to answer any questions you have, on StackExchange or off.
Go with Linode. You won't regret it. I was a customer long before I was hired.
Another thought I just had is that it's unwise to put all your eggs in one basket; I recently completed full support for the wonderful libcloud project, and Slicehost is fully supported as well, as is EC2. Regardless of what platform you choose, management tools are catching up with cloud ideals.