I've finally got my Moodle up and running (not publicly available yet though!) thanks to opensourcehost.com. I actually first learned of this host when I was trying to decide whether to use Moodle or not because they also host a site called opensourcecms.com where you can try out all sorts of open source CMS systems for free, including Moodle. Unlike the test Moodle here at moodle.org, the version there is an admin version. It allows you to try out the admin and course creation functions of Moodle before installing it. Being able to try out these functions was a huge factor in my deciding to go with Moodle in the first place.
I considered hosting with one of the cheap companies recommended here on moodle.org but after having trouble with them falsely thinking I was committing credit card fraud and not responding to the problem very quickly but instead just getting a lot of "We're such a caring host" attitude, I decided instead to pay a little more for something good. Martin had posted a message here some time ago recommending opensourcehost, and so although no one else has mentioned hosting with them, I decided to try them out.
Opensourcehost is not as cheap as some of the other sites recommended here, but it is cheaper than the Moodle Partners currently listed so it offers something for those who can afford to pay a little more for some extra services but can't afford the Moodle Partner prices. Opensourcehost will install any version of Moodle for free for you, and if you wish to upgrade to another version of Moodle in the future, they will do this for free too. You can also ask for customization of the installation-for example, I asked for extra language packs to be removed and the questionnaire module to be installed as well and this was done.
The amount of disk space and transfer you get is a bit limited but they also don't crowd their servers with a lot of sites so that will help with performance. And if you mention the opensourcecms site as the referrer when you sign up, they will give you extra disk space and transfer for free.
Scott Goodwin who owns the company was very quick in responding to all of my emails, getting my Moodle installed, and helping me to troubleshoot some problems I had initiallly with configuration that seem to have been due to my use of Firefox 0.8 (now I've upgraded to 0.9.1 and the problem has disappeared).