Hostgater and gogethosting are running well with Moodle. both have the latest PHP, I know because am using both of them with moodle 2.7.1, and I'm surprised neither of them have informed you of this. They are both very helpful and knowledgable, if you have a problem.
You'd be better off asking them about how they handle CMS and LMS. No, they are not Moodle specialists, and I'm not the only Moodle user satisfied with their services so far. But there are a lot of hosts who have no idea what they are doing and are not helpful, and looking at recent posts here the biggest, being Godaddy, is not a good idea for Moodle users.
As far as Gnomio, I personally wouldn't use them seriously, but they are certainly useful for a newbie to join for free and explore the possibilities of Moodle. And what do you think about Moonami? Are they suspicious? They look pretty genuine to me. Again I prefer having a carefully selected web host. To avoid disappointment only risk a 1 month payment deal, you could always go for an annual agreement once you are satisfied with their services.