I would also recommend www.surpasshosting.com . Other budget webhosting companies with good reputation for uptime/support are www.hasweb.com and www.totalchoicehosting.com . Nearer to home, you could look at www.webfusion.co.uk ...which also provides generous webspace allocation and bandwidth and has an excellent uptime record... although you would have to install Moodle manually here, since no Fantastico is provided. ( In fact I have always found it more convenient with upgrading to do it this way...)
Alternatively, why not install 'Moodle for Windows' ....on your laptop/local PC ? http://goohio.com/moodle/ . Then you can become familiar with Moodle/construct and develop courses, before you go live.
You can also look at the demo of the features of Moodle