If your looking for something easy to manage, free and professional. I would recommend Mybb, because plugins are upload and install through the ACP and the styles are easy to customize or make your own.
I would say always go with paid hosting for any software you use. You could start of with maybe free hosting just until your forum takes off but really paid hosting is they way to go. There is alot less restrictions and the speeds and uptime is normally a lot better. Free hosts quite often restrict the use of sending out emails (or severely limit the number of emails), some restrict .htaccess files, some have silly db restrictions like some restrict the number of queries per hour your account can make and some have such silly low phpmyadmin import max file size limits.
For paid, definitely IP.Board. It is tons better than vBulletin and has a lot of great features. I have used tons of forum software, and IP.Board is definitely the best.
I am using SMF For Free as of now and they are seriously easy to work with. Not so much pressure as far as installing mods and stuff because you can do "addons" right in the ACP! It's great. http://www.smfforfree.com Why they have SMF 1, 2, 3, and 4 for subdomains, I don't know. They go something like this
Yeah, I know. I don't know why they feel the need to have 4 subdomains. You would think that one would be more than enough, wouldn't you? But honestly, I love SMF For Free because of it's ease-of-use, everything's done right in the ACP, you don't have to know FTP or anything of that sort. I'd highly recommend this hosting site to anyone who's new to running a forum!
vBulletin is a really good forum software, my favorite actually. But the price is high (100 USD for a leased license and 180 USD for and owned license).
phpBB's moderation capabilities leave... a great deal to be desired. MyBB is a bit better but its admin interface is tedious.
SMF is probably the most mature of the major software packages at this point, though I'm honestly planning on porting most of my non-SMF sites to Drupal.