I do want shell history with folders.

I tried a few (Atuin? McFly?) but the performance wasn't good with my massive zsh history (going back several years).

Zsh+fzf does a buttery smooth job (no folders though, unfortunately). Other tools start to stutter at scale.