Well, it actually depends on what kind of board you want to run, Perl Based, Php Based, Maybe you want a windows host, and you want to run an Asp Based forum.
I would recommend a Php Based forum, using a mySQL Database. The best FREE software out there is probably PhpBB, there are other forums out there, PhpBB is the one I like. But Invision was really great, I favored invision, but they started charging. There is also the SMB forums.
Hmm, I was going to type about Ikonboard, which I havent used in about 5-6 years. Last I saw, they were still using Perl, but I looked, and now they are using Php, so that may be another consideration for you. I am actually going to check them out now, because when I was first starting out with sites and forums, I favored IkonBoard over Invision just for the fact that I didnt wanna pay for hosting to support the mySQL database.
You also need to consider how much traffic, or members you're going to have. The higher the traffic, the more bandwidth you'll need. If you're going to have tons of posts, and stuff, you going to need more space.
Try looking for a host. The host I use is
http://zephyrhosting.net (I dunno if posting that link is allowed, but im not the owner of it, im just sharing my experiences with them).
They offer 2gb Space, and 100gb transfer for $9/month.
The hosting is decent, hasnt gone down since I have had them for the past 8 months. Any problems, or support issues are handled in a timely manner. They give you an account with their support ticket system, and the tickets are answered fairly quickly.
If you're looking for more space and bandwidth than that, then you'll probably have to pay a lot more. But, what would be a good thing to do, is to go with cheap hosting, and a decent amt of space and bandwidth. Then after your forums grow, and people start to visit them more often, and they become busy 24/7, you can look for a new host with more space, and bandwidth.
*EDIT*
I checked the site once more, and downloaded IkonBoard, and they actually still do use Perl. I thought I read Php when I posted this, guess its not, lol.