My iPhone Address book, with about 400 entries, is pretty darned slow ...
... The Address Book is very slow to launch (4 secs on my phone), but Google Mobile search also searches the Address Book -- and it's fast...
My Palm address book, with about 600 entries, launches instantly. There's no perceptible delay.
Time to select an address on the Palm? Maybe 1-2 sec. On the iPhone? Maybe 6-7 seconds. (Faster if you use Google Mobile.)
The iPhone has, of course, at least fifty times the processor speed and more than 1,600 times the memory capacity of the original Palm.
The Palm had essentially instantaneous responsiveness from day one. It was one of the design goals of the original team. The Palm was to have instant on, no user waiting for a system response, and no crashes. Incredibly, the original Palm team met those goals. Later ... well, that's a sadder story.
Apple will one day fix the iPhone Address Book problems. Heck, Google Mobile already has. It is a good example, however, of the random walk aspect of progress.
The iPhone does a lot that the Palm never could, but the original Palm did a lot of things well that the modern iPhone does poorly or not at all. Technological progress is squirrelly.