OP here, thanks for the amazing comments. Some nice projects to look into!

As much as I love z, I'm also a fan of fzf, both are really complementary. I'm using this little piece of code (not from me, but cannot find the original source) to fallback to fuzzy search when z fails to find a result or when no args are given:

  unalias z &> /dev/null
  z() {
    [ $# -gt 0 ] && _z "$*" && return
    cd "$(_z -l 2>&1 | fzf --nth 2.. +s --tac --query "${*##-* }" | sed 's/^[0-9,.]* *//')" || exit 1
  }

I also use this approach in a few other places in my workflow (git checkout, vim, etc). Expect a blog post covering this in the near future.