Well, before Apple, most phones were appliances with fixed software; there was no openness to speak of. That said, I wish they hadn't continued this trend and instead took inspiration from Windows Mobile.
But then came Java and Wap. You could, in theory, download a jar from a site and try to run it. God knows if it would run. But it wasn't a locked-down app store that bypassing would land you in hot water.
"Sometimes" doing a lot of heavy lifting.
Nokia had an app store, and before you could see the available apps you have to first choose your phone: because even with-in Nokia's own product range there was so much variation in screens, keyboards, and general capabilities that they had to pre-apply a filter to show you what would actually work.