How did Cydia protect its users from SEOing apps that require unnecessary permissions? If by the fact that it’s a niche store used by only hundreds of people, there’s bad news.
It didn't protect you at all, it was more of a package manager GUI than a proper store, it just had some repositories where you could upload paid packages. And generally, you wouldn't really install apps from it (with both notable and non-notable exceptions, of course). You would install 'tweaks' which normally were iOS plugins/modifications of various sizes and functionality. They all had root privileges an a lot of it was trust based. I don't think there have been a whole lot of malware distributed in this way.
An alternative store with open-source apps, without the opening of the jailbreak and that could be verified by users, would be a good amazing start.