Another point is that very little about pre-iphone phones was customizable. I can't even remember downloading any apps before the iPhone. Custom ring-tones were therefore one of the few outlets for making your device your own.
I didn't feel the jump to a "smart phone" was particularly big at the time, actually.
As I recall (details fuzzy), He had to pay a substantial fee to the carriers in order for his app to be quality reviewed. If it failed, then he would gave to pay again. For each phone they supported, an extra fee was required. Also extra fees for different carriers, even if it was for a device already approved by another carrier.
Simply... in the days when the carriers ruled the waves, there was no profit in a healthy app dev community. In the UK, my first experience of a healthy app eco-system came with the dawn of the Palm Pilot.
I'm pretty sure I've downloaded a bunch of games on my Sony Ericsson K700/750i/800. I believe they were just Java (jar) files that you download from some semi-shady-looking website that usually used a .mobi domain via a very expensive mobile data connection.
Granted, that's just a couple of years before the original iPhone, but I believe that the first iPhone that came with the App Store was 3G.