I'd prioritise a simple getting started guide. It only has to be a page or so, but something that explains how to run the program, and achieve a few simple tasks. It's far easier to go from a simple case to a more complicated case than it is to go from nothing to even a simple case.
To pick on a specific project, Treetop http://treetop.rubyforge.org/ has a pretty detailed set of documentation (human-generated, not automated), but I found it quite hard to go from the abstract enumeration of its features to actual working code. So hard, in fact, that I wrote up an introduction to help others, and it's been a very popular page: http://po-ru.com/diary/getting-started-with-treetop/
I want a conceptual overview, usage examples, and some discussion of edge cases.
I've rabidly documented my Rails authorization library, and I'd attribute most of the attention it's gotten to the documentation.