VBulletin is the best paid software but can't do a forum host unless I buy a license for each forum. SMF for me is the best free forum software.
You can customize the default theme with style sheets and headers and footers.
If you are looking for full customized theme boards you can try out my other service at
http://www.createmybb.com