The problem with shared hosting is that you're at the mercy of having to compete with hundreds of other websites for the hardware resources, so often your site will run slow because so much is going on. You probably don't need a full-blown dedicated server, so you can look into a VPS (virtual private server) which is sort of in between shared and dedicated as far as price, but you get dedicated hardware resources for your site(s) so the performance is a lot more consistent. Google VPS hosting or look on webhostingtalk.com, there's a lot of good options out there.

What host do you guys think I should get then that is reasonably cheap?

How cheap are we talking?

What's your budget and what are your requirements (bandwidth, webspace, etc.)?

Like I am willing to pay 20-30 dollars maximum a month. All I want is it to run fast. I hate this waiting and sometimes it doesn't even load cause it takes like a minute to load.

A possible solution here leads to a question of my own. 1st of all, are you regularly optimising your database? I have found this dramatically improves the performance on my own board.

Secondly my own question: Does anyone know how/if it is possible to schedule this task to run automatically? At present I use phpMyAdmin to optimise the database tables, and due to the installation of several hacks it needs to be done daily.