For simple requirements, I would recommend Linode or DigitalOcean. Both gives total control of your box and requires system administration skills.
If your concern is scalability, I would go for Amazon Web Services. But aside from system administration skills, it will require you to learn AWS interface and/or console thus with the learning curve. But if you master how AWS works, scalability won't be an issue anymore.