I have 925 books on my PRS-505.
My collections cover 13 pages. Reasonable navigation time to any series or category. If I was reading a series to get to the next book I just have to press the menu button twice then select the next book.
The following 2 items were timed events:
1. I just added the 926th book using Calibre and it took only 3 minutes and 35 seconds to complete the re-indexing after removing the USB cable.
2. Just for fun I just shutdown my reader. I have set the select button in the middle of the navigation to power it down if I hold it in for 5 seconds. I just turned it back on, it took 1 minute to get past the restarting screen, then only 3 more minutes to finish its start up. I was able to press continue reading 4 minutes and 4 seconds after I turned it on.
This doesn't sound horrible to me.
PS. The other day I cleared the reader and put the 925 on from scratch. This is an estimate, but I recall it taking around 20 minutes to index all 925 books and be ready to read.