Within the past year, I started a successful Invision Power Board (IP.Board). It's the other large contender in premium forum software.
Love IPBoard. Solid software. Contemporary design and coding decisions. After using vBulletin for so long, IPBoard feels like a forum platform made by the guys that created Wordpress. Very useable, solid administration backend, and includes a lot of core functionality that vBullet painfully doesn't have.
Scales very well out of the box. Low performance requirements. Highly recommended.
It's also very easy to skin if you know the basics of CSS.
Pretty much the status quo for free forum software. Massive community. Massive amount of modifications. Every question you have has been asked. Highly recommended
I doubt I'll ever pay for forum software again. It's unnecessary and support isn't that helpful anyways. The only real problem with forum software is, down the road, high load on the server. But that's such a big cross-that-bridge-when-you-get-there issue and there are plenty of resources for all forum platforms.
Runner Up: Simple Machines: Clean. Good performance. But I only did some coding work on it for another forum and didn't get a big look at it beyond what I saw.
Those are the only platforms I have experience with. My basic advice is to try IPBoard out (they have a free trial hosted right on their website) and then give some free options a try. Explore the respective communities and make your decision based on what feels the best to you and what community seems to be able to answer your particular questions the best.
I own an active vBulletin forum (for three years now) that averages 1,100 users logging in each day, and I highly advise against going with vBulletin. Ever since v4.0 and the buyout of the original developer, vBulletin has had an increasing rift in its community. It's been over a year since v4.0 has been out and I, along with many other big board owners, are staying at v3.8.x for the foreseeable future.
I'll change forum software before I upgrade vBulletin. In general, vBulletin feels like you're dealing with sold software, and you really are. It's meticulous and badly designed. vBulletin was great in the mid 2000s, but current vB feels like they just kept monkey-patching their core product rather than renovating it.
HOWEVER, due to vB's entrenched popularity, it has a great modification community with a huge assortment of modifications. But a lot of them are just making up for core functionality that vB lacks, or they're bells and whistles, or they're modules already replicated on other forum softwares.
vBulletin also scales pretty poorly out of the box.