A big part of Android's problem is that the permissions model sucks. Until recently, all permissions requested by an app had to be granted up-front as part of installing the app. Apps tended to request anything and everything for no good reason. This trained users to just click through the permissions screen without paying any attention to it.

The iOS model (and now Android model) of prompting for permission when the app first tries to use it is much more solid. If an app requests access to your contacts for no good reason, you'll get a fairly obvious prompt and you can say no. There's still some trouble with getting users to pay attention, but it's a lot better.

I don't see how this makes a store appear necessary. Android doesn't allow sideloading by default, and iOS can now sort of sideload apps using the new free signing stuff Apple put out. The limits on the number and duration of sideloaded apps make them impractical for selling legitimate software, but are no obstacle to malware.