vBulletin which is not free is the best forum software.  You can see it in action at several hundred different forums including 
DVDTalk, 
WebHostingTalk and 
HTTPme.COM.
I would not recommend using vBulletin right off the bat unless you KNOW for certain that you're going to have over 5,000 members with at least 50 active members during any given moment.  If you realistically know you're going to get this kind of traffic (or have really good advertising) then get vBulletin.
Instead I would recommend starting with 
InvisionBoard forum software which is free, efficient, powerful and has a nice clean look to it.  My 
forums uses InvisionBoard forum software and so far I LOVE IT!
So if you want the absolute best and don't mind paying for it then get vBulletin but again I think it's overkill.
The BEST free forum software is InvisionBoard, although it's free it's still quite powerful and customizable.  The best part is how EASY it is to install and maintain, I am a total forum newbie and I've learned everything just by reading the manuals, asking people and playing around.
For hosting you could spend $5/yr to $20/mo, what is your budget for hosting?  This is where you do not want to go cheap.