Have you used fish? The built-in fuzzy matching works pretty well for me. Wondering if there's any reason to add atuin in. Sync seems like a negative to me more than a positive.
I use fish with atuin but without sync. It is nice because I can search commands for a given workspace. For example the commands within a given git repository.