Different hosting situations offer different "shares" of an actual machine. Cheaper plans give you a portion of hardware and connection. The limit isn't really the number of user accounts, it gets hairy with the number of simultaneous users. You'll quickly exceed some of the cheaper plan's limits if you have tons of people hitting the site.
I've used Fatcow, MediaTemple, and SiteGround. All are pretty easy to setup and offer a range of support plans. I think SiteGround and Fatcow offer EZ setup wizards for configuring Moodle on a site as well. I pay $109 for 2 years of Fatcow hosting with one of the budget plans. I wouldn't trust that level of plan for more than 50 peak simultaneous users. Even then, hiccups would be had.