Hosting without service
Your use of a web host will likely be made most enjoyable if your web host offers a current version php with the requisite extensions and access to php.ini. See Installing Moodle - Software with respect to php and mysql requirements.
You will likely want shell access, via ssh that will allow you to manage files from the command. This eases making changes to htaccess files, php.ini and conf files. You should of course determine if your web host allows access to various Apache, php or mysql configuration files, as some web hosts either preclude such access or provide only limited GUI tools for this purpose.
You will want sftp so that you can move files to and from the server without having to rely on php to accomplish this.
You will also want to confirm that you have access to phpmyadmin or mysqladmin so as to be able to easily manage your mysql databases although, if you have access to your mysql host, you can manage via command line. ssh support with sftp, access to phpmyadmin.
You may find yourself with issues regarding e-mail, as that is an area where web hosts can often be sensitive (both as to spam and as to bulk mail, which are not necessarily synonymous.)
Some web hosts may also offer automated installers. Some of these installers are wonderful options, some may create more trouble than if you installed manually. The Moodle forums are fully of discussions of issues with various installers at specific hosts. Fantastico is a common example, while some web hosts like DreamHost have custom scripts. Many hosts now offer GUI "panels, such as Cpanel, which provide GUI tools to manage mail, databases, application installs etc. We encourage users to supplement this documentation with information about installers and panels at various hosts by editing the web host matrix referenced below.