I think other manufacturers allowed that as well, but I could only use the "free wap browsing trick" on Nokia phones, so I never explored that.
Finding a .jar file that works on your phone was the biggest. Games often only supported a single screen resolution and so there were multiple .jar files for each game and you had to find the right one for your phone. Also sometimes even if you had the right screen resolution the .jar just crashed when you started it without any clue as to what's wrong (probably they needed more RAM or some platform specific code, but I was in high school back then so I didn't know much more about it)
In the early days, there was also the issue of how to get that .jar file to your phone. I distinctly remember old Nokia phones could download them through WAP (which was paid) or receive them through IrDA/Bluetooth, but themselves couldn't send applications through IrDA/Bluetooth (I think Sony Ericssons were the ones which could also send them....), This issue was later solved by microSD cards and USB cable transfers from PC.
Pirated JAR/JAD files were definitely hit and miss, but I don't think those are a great example.
Then the first Android devices arrived, with the Android Market (long before Google Play) that did allow you to download apps. But most people again maybe they didn't have internet, or more simply wanted pay apps but didn't want to pay for them, just exchanged .apk like it was the norm. (Pirating by the way was much more present than these days, for example I don't recall a single person having a PlayStation without the modchip, and burned PS1/PS2 games where the norm).
It's only with the arrival of the iPhone that this was no longer possible. In fact I recall that the criticism of the first iPhones, till the iPhone 4, was that it was an overpriced device and that it did lack of the possibility to install applications and exchange files with bluetooth, like everyone was used to do. The iPhone was a niche product that was not diffused (when I was at high school I recall maybe 1/2 people having iPhones, all other one Android devices).
The thing on cellphone operators is maybe an US specific thing, I don't recall having anything like that in Europe, more specifically in Italy. Quite frankly till 10 years ago using the cellphone network for internet was unthinkable, because the prices where so high. Then arrived the contract that give you 100Gb of data a month for 10 euros, but back in the day internet was expensive, to the fact that just by pressing the internet button on a phone it did consume all your credit. This is probably also the reason why WhatsApp become so popular (you could chat with your home internet connection that now everyone had without consuming expensive SMS)
For pre-iPhone cellphone users, your cellphone network operator controlled access to what apps were available for installation. This is was the most common, if not the only, method for cellphone app distribution. App makers (mostly java games) paid to get on that first page of downloadable apps. I'd add some references but Google seems to have amnesia about anything cellphone app distribution pre-iPhone.
Apple didn't have an app store initially. How Apple convinced cellphone network operators to cede app approval/control, I don't know. Perhaps it was "apple's way - take it or leave it".