Like Brent Simmons, I remember buying software online over a decade prior to the App Stores, although I was at the consuming end and he the producing end.
We shipped NetNewsWire 1.0, an RSS reader for Mac OS X, in 2003 and sold it over the web for $39.95. There were no boxes and no printed manuals — there was nothing physical at all. This situation was, at that time, completely unremarkable: it was expected.
We used a service called Kagi for the storefront and credit card processing. Kagi had been around since the ’90s, and it was well-known and trusted by the Mac community. Setting up our account and store was pretty simple — simple enough that I forget most of the details.
Part of how it worked was that we had to upload a text file to Kagi’s system, a file with license keys their system would give out one by one. I wrote a script to generate that file, and I wrote code in the app to validate a license key. I also had to create a small window where a user would enter their license code.
This meant there was some work, yes, but it was nothing compared to what you have to do to sell on the App Store.
I remember Kagi, and there were many other similar services around the globe. It wasn't always completely smooth — credit card processing would occasionally hit a snag and fail, possibly because it saw transactions as possible fraud, or was just having a bad day, and licence keys might take a while to reach you or not show up at all — but overall it worked.
And — importantly — Kagi’s fee was something like 5%. (Update a little later: evidence suggests I may be misremembering: it could have been more like 10%.)
Even more importantly: Kagi didn’t review our app. I suppose, if we had been selling something egregious in some way, they might have learned of it and cut us off. But that’s a standard business relationship. Kagi was not a gatekeeper.
Kagi didn’t promote our app, either. It wasn’t their job — it was ours. They provided a storefront and trusted credit card handling, and that was all we wanted, and it was great.
And there were plenty of sites out there where new software could be promoted, notably the venerable Tucows (RIP).
The App Stores exist not to replace real-world retail for software — that was already in decline, as Brent mentions — or to make the purchase process 'safer', which it has never achieved. They exist to exert control over both developers and consumers.