Someone could start an App Approval business. Applications don't require approval to go on to an app store / market place, but if the developers submitted their code to one AppApproversLtd, those guys could review it for a small comission, then upload it to the app store as a trusted application. Though there's a slight conflict of interest (i.e. the person paying the approvers is also the person sending the code) I believe it's in the AppApproversLtd company's interest to do a good job since their business depends on them giving a reliable evaluation / building up a good reputation.
Using that business model keeps flexibility in place, where users decide if they want to risk trusting an unapproved app, or would rather go for an app that's been approved by one of these companies (potentially incurring additional cost if the developers passed the approval cost on to their users rather than offsetting against advertising).
AppApproversLtd could offer different levels of approval / ratings - i.e. just checking for malicious code vs. checking for polite error handling, efficiently written code, best practices, impact on battery life, etc.
That would be fine but it doesn't solve any of the problems really. Apple will still have control over their store. Google Play will continue to let you in and then review if they get a complaint (at least I assume that's how they do it). Ultimately I'm not sure that the business model will work. It only really applies to Android and even then most people get apps through the marketplace. Those people who want to side load apps most likely know the consequences or know someone who does and decide whether or not to take the risk.
It seems analogous to running your website code through the W3 checker. It's a certification that you did stuff right, but it doesn't stop most users from going to your site if you don't have that little badge at the bottom.
Using that business model keeps flexibility in place, where users decide if they want to risk trusting an unapproved app, or would rather go for an app that's been approved by one of these companies (potentially incurring additional cost if the developers passed the approval cost on to their users rather than offsetting against advertising).
AppApproversLtd could offer different levels of approval / ratings - i.e. just checking for malicious code vs. checking for polite error handling, efficiently written code, best practices, impact on battery life, etc.