Most of the things that were amazing about the iphone I had in my Samsung sph-i300 palmos phone 6 years earlier.
In many ways the palm device was more amazing since it was already a rich mature ecosystem by then and already had 3rd party apps, thousands of them, for every imaginable purpose.
It was the essense of the later iphone (after it allowed 3rd party apps) 6 years before the first iphone.
I don't remember any gap. I certainly had an unbroken sequence of pda phones from several makers after that, but maybe there was a time before 2001 where people didn't use pdas much?
I never used straight non-phone pdas myself.
I was playing with a wince pda for a while but only for stunts like getting an old dos version of my companies unix software to run in a dos emulator on a Journada, just to show it at a company xmas dinner to the guy who invented & wrote the language and db initially on the trs80 (he immediately closed that and tried to find porn, I love that guy).
To me a pda was never that useful by itself, only when Kyocera combined it with a phone a year or two before that i300 did it become a must have for me.
But the way I remember it they seemed to be pretty popular with everyone else.