Well, do you have to have the PDFs created on the server side?  Was going to suggest that OpenOffice.org does PDF creations pretty well.

I'd suggest stepping back for a moment and deciding if PDF is the best format for you. What are you trying to accomplish? Given that PDF is generally a terrible format for online viewing, you may want to think about other formats (such as HTML). PDF is good for a document if its main purpose is to be printed on dead trees. Otherwise, as PDF is oriented towards printed pages, I'd try to avoid it.

Then, do you need to really create these documents on-the-fly, from fast-changing dynamic data on the server, or could they be better built on a PC and uploaded?

Since your material is going to end up as ink on paper, PDF may be a good fit (especially if you want to do layout for specific-sized paper, and online display is secondary). One path you should look at is running the PDFLaTeX markup system to generate PDF files. I think I've heard of LaTeX being run on LP servers, but you'd have to check if it's installed already or if you'd have to go to VPS or dedicated (it's C code... I don't know if there are PHP or Perl versions of LaTeX). If you can come out with a plain text flat file (or some other word processor format), there may also be converters (to PDF) that can run on LP. Just keep in mind that interpreted scripts (Perl, PHP) should have no trouble running, while compiled and linked binary programs will be a royal pain to get up and running on a server. Once you have a PDF file and the user downloads it, do you have some mechanism for destroying it so that space isn't wasted? Perhaps a cron job that goes through and deletes every .pdf file more than 24 hours old?

On the other hand, if the material is primarily for online display, with printing secondary, I'd consider HTML+CSS, with a "printer friendly" CSS version for output device "printer" that can fit to specific paper sizes.