They don't require much to run - I've used phpBB and SMF. Personally I like SMF because it has a function built in to easily add in plugins (and there are a lot of them). I'd say use the latest beta release of SMF - anti-spam is much better and much better features.
Most hosting accounts support these, I think you'd have to go out of your way to find one that doesn't. php support is pretty basic and most give you at least one databas (usually MySQL).
1&1 and Host Monster both can run phpBB and SMF (and I think that is pretty close to the lowest end of hosts).

I don't think many other hosting companies will have an issue running these.