I never really used any Hosts apart from a Forum-Host and just a regular Free-Host.
The Forum-Host was CreateAForum. A Host that did all of the Hosting for your SimpleMachines Forums. There were Subscriptions for optional Features(Like Translations) but the whole Service was free.
The Free-Host was x10Hosting. I used them for a lot of my Forums from there but soon after losing interest in Web-Development, I just stopped.
I don't use Web-Hosts anymore. Unless it's for an Open-Source Project, in which I use GitHub Pages.
I currently use hosting through work so it doesn't cost me anything but I am going to be using Name Cheap pretty soon for helping a family member get a site up for their traveling adventures/mission work.
Do not compromise what had been planned about for the web site just to meet the level of what can just be offered with the cheap web hosting package. Try to search for other cheap web hosting packages that offer the applications needed for the web site.
Read other clients' or customers' testimonials. Try to contact the current customers of the web host provider of your choice and see if they are satisfied with the kind of services being rendered by the web host provider.
It's true, many people aren't aware of how inexpensive web hosting is. The key is finding a web hosting company that can provide excellent customer support.
Currently using HostBlast and are really happy with their gold plan. They are really cheap compared to other hosts who offers the same package. Their support is fenomenal (fast and helpfull). 5/5 from me 😀