I was just wondering if I could use a different host, or do I have to use one of the two hosts suggested for a budget hosting plan?
Concrete5 is open source, so you're free to download and host it anywhere.
I've been using InMotion Hosting for years with no issues to host C5 sites. I've also used others such as HostGator to host C5 sites as well.
You can use any hosting provider you want. Can even host it yourself if you wanted. I use Siteground for all our hosting needs. They provide great hosting, easy to use interfaces and blazing fast servers or PHP applications.