PHPBB is a good bulletin board system, widespread and with a resourceful community, but also too big and demanding in terms of computing for certain uses. Many functionalities have been added step by step and that's not always the best solution. Invision Power Board and vBulletin (the one we use here) are excellent but if I recall correctly don't have free versions (just evaluation versions, which you're entitled to run for a month or so).
I'd personally go (well, I do) with PunBB (punbb.org), is lightweight, customisable and provides practically everything I need (and none of the silly stuff I have no use for, and I include PMs here, even though there are user-developed mods). It may or may not be what you're looking for but at least take a look. Oh, and last time I checked there was an interesting new one, a very elegant but lightweight bb called "blackboard", but still in the works.
Edit: Oh, about what you need... any hosting with php and mysql, for any of them, that's it. They are all very easy to set up.