Great idea!, there are lot of options on webhosting and the key is to find the right folks for your business and skill set. I have done this couple of times and learned something new each time (the hard way!)
If possible, I would get a dedicated server, even the cheapest one will do so you have the freedom to make any changes as you like. Virtual servers are ok but I got better deals and performance from dedicated server. In my personal case, Moodle hosting companies didn’t quite work out for me because of the lack of flexibility, in our case we couldn’t forecast accurately the number users, concurrent users, data transfer rate etc. and most moodle hosting companies has some limitations on those . You should also look at what type of skill set your team has. Even though we had pretty good technical folk, we went with managed hosting so we can focus on the core issues rather babysitting the server.
I am not sure I can post the vendor names here but if you like, send me a message or email, I can give the hosting providers we use. I have absolutely no business interest with them we just use their service