Either a directory structure or, better yet, user definable categories (ala MobiPocket). The existing linear structure is not very good as collection grows beyond a few pages. If they are feeling ambitious, the ability to assign more that one category would also be nice (IE: Classics, Mystery, English...)
Flags associated with each book -- and a filter to include them in displays, exclude them from displays, or display them exclusively. Flags: New, Completed ... Other user defined flags....
Ability to redefine page turn button behavior. The way I hold my device, my left thumb sits over the PrevPage button. It would be nice for me to be able reverse the functionality of the Prev/Next page buttons. Future hardware editions need to completely re-think those controls anyway. For that matter, it might be nice to enable any of the keys on the keyboard as Prev/Next buttons. Some users might be better off completely disabling the side buttons (they do cause a lot of accidental page turns when picking device up or putting it down) and allowing some other USER DEFINED key to do the page turns. Easy firmware fix (workaround) to an ergonomic design flaw.