> Goes without saying, but bash-completion. Fish's completion is mostly history-based, which is great for repeatedly running the same command, but terrible for discoverability

Fish has both kinds of completion. You can hit tab to get a list of possible completions (command-list based) if there is more than one, if there is only one possible command it will tab-complete. You can also customize this list.