First, security in the payment process. Apple seems to doing pretty well there, so equivalent or better than that.
Second, offer a guarantee that the software on offer is free of malware and unreasonable tracking. Some degree of inspection and curation would need to be performed by the selling App Store as well as having agreements set up with the developers of the apps.
Third, real penalties to all parties if there was some sort of breach or other malfeasance. In the case of data leaks and other issues from the store, the penalty would fall on them. For malware, etc., the penalty would fall on the developers and/or the store for lax practices.
What does this mean? Apple's app store doesn't even guarantee security.
Would something like F-droid be allowed? Because if not I would argue we're still not solving the problem.