If you need a smaller installation (20 gig and under) I can get you set up on my shared hosting platform on a Redhat Linux box with Fantastico, MySQL and Moodle in an outstanding data center. I'd need to know what you're looking for to get you an idea of cost though.
If you're looking for your own box you can rent outright you should look into this company. http://www.ev1servers.net/english/index.asp . I basically resell from servers in thier center. I've been with them for years and have nothing but praises to sing about thier quality and support. You'll be on your own with moodle setup and support with these folks though unless you get it elsewhere.