There are several options.
1. You could get a cheap vps, which would be likely much faster than a shared hosting account. The downside is you would be self hosting.
2. You could host on amazon ec2, which is superfast. Then though, you're still self hosting.
3. You could go with any shared hosting (such as hostgator's cheap packages), and maximize speed by using a cloud cdn (such as amazon ec2 combined with cloudfront).
4. Also, any good hosting company (hostwinds, hostgator, etc will help you maximize the speed of your site if you talk with their support staff about it. (There are a lot of little things you can do minimize the loading time of your site, and they'll help you if they're remotely competent.)
Hope that helped.