I should be able to define search queries with logical combinators
Summary: That is, when I'm saying that I want to do a search, I'd like to be able use AND and OR in some fashion.
Eric's example, from his Spirit Island FAQ, is being able to search on "Presence AND Blight", to quickly refine what I'm looking for.
The AND case might actually want to become automatic. We're currently searching only on literal, complete search strings. But more-sophisticated engines tend to break up the terms on obvious boundaries (eg, spaces), and consider each term separately. You get the highest score for an exact match, in-order, but you'd get lower scores for simply having both terms in the same value, or even on the same Thing. This enhancement probably isn't too hard to implement, and is why this is marked as High.
An advanced-search capability might also be nice -- allowing the user to do complex searches with OR as well as AND -- but that is clearly much lower priority.