* Examples. Realistic, complete, useful examples that demonstrate the software being used in the manner it is intended.
* Glossary for any special terminology that can't just be googled - especially project specific terminology that may be confusing, and double especially terms or phrases which are used slightly differently to the way everybody else uses them (e.g. 'user' means something slightly different almost everywhere).
* Lots of "why" describing why the software behaves in ways that seem surprising at first glance.
Seconded on examples, but example code needs to be integrated into software testing for projects that are frequently updated. Broken examples are arguably worse than none.
Even less arguable is when examples that worked are broken by an update and remain unchanged--they'll work for people on outdated versions but break when they upgrade, and also break for new users, and nothing will sufficiently explain why.
Please add your documentation examples to your testing pipeline (or write tests clearly enough that they can be good examples, and just use those).
A language specific answer: The testing package of the Go standard library has a built-in support for examples. They are executed as part of the tests, but are rendered by the documentation generator as examples. This obviously only solves the problem of library writes that want to expose examples of library usage (and ensure they don't get stale)
This is bang on - to get up and running people want examples and some context. For me it's the first thing I look for.
On my most recent project I split the docs in two; a 'guide' with example code and output - it has more of an 'overview' feel. The other half is the technical (API) docs built from comments in the source code.
It's not the most exciting project in the world, but it's a Rails form builder that meets GOV.UK requirements. Here's a draft of the guide if anyone's interested.
It's generated via Nanoc which loads the form builder and uses it to generate the example input, rendered output and HTML - in theory it can't be out of date or broken.
* Glossary for any special terminology that can't just be googled - especially project specific terminology that may be confusing, and double especially terms or phrases which are used slightly differently to the way everybody else uses them (e.g. 'user' means something slightly different almost everywhere).
* Lots of "why" describing why the software behaves in ways that seem surprising at first glance.