I think that Apple did absolutely the right thing for a young marketplace. It was bad enough as it was (remember the $1000 app that did nothing? And the game with a $100 in-game purchase of ammo?)
In any case, malware is best prevented by strong sandboxing. Forcing everyone to go through the store does approximately nothing to fight malware.
Additionally, not all malware needs to escape a sandbox. For instance, there are a bunch of fake apps that simply capture credentials, or that make expensive phone calls or texts.
A well-run store that can run tools against images is a decent first line of defense against malware. A store also provides reliable information about code publishers. These are not a complete defense, but they appear necessary.
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.
Apple seems to have gotten their trophies here (no doubt) and then stared at them rather than figured out how to get more.
To Apple's credit, they are occasionally way ahead of the curve on developer convenience, and have reaped huge benefits from that.
I tried making smartphone apps in 2003-07 for Symbian, Java ME and the very first Android beta (the one that had a traditional keypad phone emulator). The experience was always disheartening. Horrible IDEs that sometimes cost money, awful device feature fragmentation with no standard ways to handle it, inconvenient APIs designed in the style of '90s embedded platform expectations.
If you managed to get a working app together, distributing it was a mystery. On Symbian, you'd have to pay something on the order of $1000+ for certification from a "special Symbian partner", and even after that there was no central app store. There were websites offering downloads (and paid listings), but users would not stumble on those. It was a terrible offering all around.
The native iPhone SDK in 2008 changed all that. Suddenly there was a smartphone with a desktop-class IDE experience and desktop-derived APIs, with easy access to fascinating new multitouch UI possibilities... And there was an integrated Apple-curated store where you could publish any number of apps for only $99 / year! That was an amazing deal compared to anything that came before in this space. Some occasional hassles with Xcode bugs and certificate weirdness was nothing compared to the nightmare of the Symbian/JavaME style mobile dev experience.
Even before that, Apple had done well by its Mac OS X developers by offering the NeXT-originated Cocoa tools for free. Back in 2001, that wasn't the expectation yet. It was a good API, battle-hardened at NeXT already, and much better than anything Microsoft was pushing in that Windows XP timeframe. Apple's efforts to support OS X development had two major benefits: the Mac's resurgence was helped by increasing availability of good 3rd party software created by dedicated developers, and the iPhone global launch was greatly helped by the fact that those same OS X developers were able to easily move to the iPhone.