This is doubly awful because when I show a non-tech user around linux, the thing they're always most impressed by and which is most distinct about the linux experience compared to Win/Mac is the ability to pull arbitrary software from distro repos.

But the GUIs are awful. The cli experience is awful, too, but better and we get used to it. They're never going to get used to it, and why would they want to? I don't know the answer; package management is a complicated problem. But maybe some sort of distributed app-store experience where the package manager also manages marketing for and forums about the apps. See, I really don't know - but having to go to a webpage and read a bunch of marketing material then download, or go to an app store and get descriptions, screenshots, and commentary by other users is somehow a subjectively better experience for non-tech types than "apt-cache search" or its GUI equivalents.