Cheap: browse through the listings on lowendbox.com, you will find some amazing deals for both VPS and dedicated servers.
Reliable: AWS / Rackspace / DigitalOcean / Google cloud / basically any famous one.
When you're starting, it's probably better to rent a cheap VPS server. If you start growing fast, you can always move to the cloud. But modern cheap VPSs are quite powerful. I have 7 websites running on one that costs me $6/month.