Before picking a host, you need to decide on technologies used - for example, if you're using ASP or .NET, it makes sense to host on Windows (the unix type asp solutions are not the most compatible, and .NET isn't yet available (stable) for Unix). If you're going down the php/MySQL route, obviously a Unix or Linux solution is the way to go.
I run both Windows and Unix webservers, and the technologies they run all have pros and cons.
Decide the technology, then pick the host.
As to forum software, I like access to source code. Whilst I really do like YaBB, its architecture really sucks, and the next major version (not the interim one due now), which is supposed to reengineer this massive issue, has no release date. Not even a timeline. May appear next year, may be 5 years, who knows. Based on that, I cannot recommend it.
I quite like the old forums.net software, which has morphed into Community Server, but with each new release, it seems to be going away from its original market of free, open, forum, and getting more and more commercial with tighter restrictions on what you can and can't do.
I detest phpBB with a passion, more bugs that a Libyian coffe shop, and more holes than a box of Polos. Too common, too sloppy, too much hassle.