Cheapest will be Linux Hosting.
What you need to do is look for a supplier of hosting services in your area, region, country for reasons of being able to bring complaint through the various consumer rights agencies that exist, in the UK its Trading Standards with Consumer Direct handling inital advice and rights giudance with Trading Standards enforcing any breaches. The same sort of system exists in the US as will in most countries.
Because I can not explicitly tell you what service to get, you need to draw up a list of suppliers that check the boxes
[ ] - Unlimited traffic (the amount of traffic that requests data from your site can be capped and result in further bills)
[ ] - Unlimited data limit (the size of your site)
[ ] - Unlimited databases
[ ] - Unlimited email accounts
[ ] - Unlimited CRONJOBs & BASH
[ ] - Serverside languages like PHP, ASP, etc.
[ ] - No surprise bills
[ ] - 24 hour contact
[ ] - Member of a federation or guild that is industry recognised.
If you need anything specialist like HTTPS then you will have further expense because certificates can be pricey and most certificates are issued based on what they are used for, you can use a HTTPS login system that ensures that your clients login in can do so securely without having to go the additional expence to produce a full HTTPS site.
If you go with Windows hosting, then expect to be paying a lot of money out for the licences for everything that you get freely under Linux.