It's very important to have a good Linux distribution like Debian or Ubuntu where you can install/upgrade things in few seconds with apt-get.
Also it's important to have root to be able to install different apache modules, install cron jobs, be able to manage the firewalling in case of attacks (I saved myself from a DOS thanks to a Tcl script + iptables one week ago).
Virtual servers are cheap but the performance may not be bright.
p.s. I suggest to use a very low TTL for your DNS records so you can switch ASAP if there are problems. Also to try to "packetize" your application is important in order to make sure you can install without too much problems your code in a different host in little time.
Btw, you can see that I write like a child. "Scritti"? Scrivi! :-(
Amazon S3 can be used for most of the storage needs, but I'd need a lot of RAM for good price. Server Axis virtual servers seem good this far.
What about service-level agreements and terms of service of various providers, all I've seen would seem to leave a lot to be desired?