In what way? I don't see any fundamental difference between discovering GNU/Linux packages and Android ones (in the "stores" I've used -- f-droid, /e/ apps, and Aurora).

There are a few gui apps that leverage tags for browsing dpkg/apt?

Why it doesn't count? It works perfect for me. How else do you search for apps in app store? New, popular?

Algorithms that match intended words and synonyms over verbatim pattern matching. Seriously, apt search sucks because if you are searching for something that does not include the word you use, it falls over completely. Just like every single time I try and brew install a package I sort of remember the name of, it will just not give me anything.

This could be an area of improvement. E.g. I don't think adding metadata to packages would be particularly complicated and that could help (e.g. using tags) with discovery.