Linode, easy to start small and grow just by re-sizing the server. They may not be the cheapest but they have very good support and their guides are perfect.
I love Linode, but getting new IPs (a listed requirement) from Linode is like pulling teeth. You have to prove you have a different SSL cert for each new IP you request or they'll tell you to just use one IP with host-headers.