Then let App devs, if they want to do that, apply for additional manual checks. They could probably get away with charging for that check. If Apple is satisfied that the App only does what it’s supposed to and doesn’t abuse its privileges or send data to third parties, approve it and mark it as such.
Some kind of badge prominently displayed on the App Store marking that App as “checked by Apple” or something.
Give App Store users an option to hide Apps not checked by Apple.
Sure it gives Apple even greater power as a gatekeeper but I think the benefit to consumers caring about privacy outweighs that.