Out of the box phpbb3 is not that good, no description, titles are bad, numerous duplication issues through pagination etc. However there are many modifications for fixing most of these problems. It's still not gold yet so the mods will only increase over time. Most flexible system IMO simply because of the vast amount of people writing mods for it.

Anything better that requires a paid license?

I get some hits to vBulliten forums though Google searches.

Check out bbpress
[bbpress.org...]

So far all suggestions seem to be PHP based.... including bbpress

You might want to check out Plone.org and Zope.org

No licenses but they are NOT PHP based... they are Python based.

I have spent months optimising my XMB board. I don't think that there is an easy answer it just requires work.

In someways the forum software is the antithesis of SEO. its designed to show extraneous data and have multiple urls pointing to the same information.

After much work I am now seeing a huge increase in Google visits. Now about 1/2 to 2/3 of all visitors are coming straight from google and other search engines. I rank high in many of my threads against vanilla html pages.

It can be done.