Create 3-5 different search algorithms, with names and understandable characteristics, then let me choose which one when searching. You may have some algorithm that prioritizes recency, or rapid changes, or more interaction, and others that prioritize longevity, citations/links, others that prioritize that type of information - prioritize regional or noteworthy events over historical info, etc. Have some algorithms that penalize spam/linkfarms more heavily than others. The git/so spam farms that come up when I search for an error message are simply useless, and would love ways to switch away and try other algorithms, without necessarily having to switch entire search systems.
Have algorithms that explicitly take in to account the search/click behaviour of others. Let me choose to have the search behaviour of friends/colleagues/famous-folks explicitly included or excluded in search results ranking.
Let people easily switch between multiple algorithms, and let 1000 gardens bloom (or something like that).
Also, determining better ways to 'search' non-text stuff. If virtual worlds become a thing, finding ways to 'search' those (whatever that might mean) will be big.
Image search still has a long way to go, IME.