Your requirements are in fact pretty easy to fulfill. The vast majority of hosts should be able host that.

Now, HD is based on a paid forum software (vBulletin), and it won't be distributed by hosts, but there's lots of quality free forum software out there. You can get a quick look at some of the more popular ones here: http://www.opensourcecms.com/

Most hosts will also be offering a tool like Fantastico, that allows easy installation of applications, including some forums, but personally, I recommend manual installs.

Among the free ones, I recommend SMF (SimpleMachines.org), as it comes with quite a few features out of the box.

You need to keep in mind though that the host only provides a platform to host your site, but won't be creating, running, customizing the site for you. Those are the jobs of other people: webmasters, designers, programmers.

EDIT: Always have a sufficiently recent backup of your site files and, most importantly, the forum's database.