As Logforme noted, hosting providers need not be involved in your hidden services. You merely install Tor, point your server at localhost, and configure the hidden service in torrc. You also want routing and firewall rules that block any connectivity except through the hidden service.
Of course, providers do need to allow connections to the Tor network. However, these are very much like client connections, rather than relay connections, so they shouldn't attract attention (until adversaries track you down, anyway).
It's most secure to isolate your server(s) and Tor process in separate machines, or at least in separate VMs. That makes it much easier to prevent leaks. And if adversaries exploit weaknesses in your server(s), they can't get at Tor quite so easily, and call home from your public IP address.
While I have no clue what NearlyFreeSpeech.net said, it's possible that they were considering the possibility of providing pre-configured Tor gateways. Doing that with web-hosting accounts would be totally insecure, but very user friendly. For VPS customers, they could provide Tor gateway VMs. That would be somewhat more secure, but they'd still own your hidden service key(s).
Regarding user194's statement "If you're using a 3rd party hosting company then there's probably not much reason to anonymise the server, since you don't own it.", I disagree. No matter how anonymously you're renting the server, there's probably some connection, and another layer of anonymity never hurts.