I can recommand you to read discussion http://moodle.org/mod/forum/discuss.php?d=1870 with a lot of good ideas.
Be aware of verry cheap servers: you do need to have some processortime available for good performance.
Welcom to the club. Before continuing, read the concept Oodle-Moodle in "glossary of common terms"
I don't know if we are allowed to blow our own trumpets here. I do have a small interest in www.totalqualityhosting.com who have served me pretty well. I think they are good value at US$50 per year for educational use and double that for commercial.
You may find cheaper elsewhere, I don't know if you will get the same value.
If you can speak Japanese there is a free php Mysql server at
I am not sure that it will run Moodle but it runs various CMS, such as LDU, Xoops and the nukes.
You only get 50M so you may be advised to remove the languages and modules that you don't need. But then again who speaks Japanese?
I would be interested to know of any other free Mysql opportunities, since I would like to offer other teachers a test moodle installation.