I like the idea of adding some additional links beneath search results. In addition to category info, there's also the kind of info that's currently in infoboxes (but which would properly be better sourced from Wikidata at some point in the future)—I'm particularly thinking about the case of a movie, and having actors, directors, the film series, etc, or for a book having the author, publisher, etc.
For both categories and Wikidata there's the difficulty of choosing which info to include and which to leave out. Some articles have dozens of categories, and some categories are pretty boring (either because they are too abstract, or because they have so few entries in them)—so ranking them seems necessary.
DCausse also suggested using Portals rather than categories when they are available, which makes sense since they are more organized for human consumption.