I second onthegomom's Lego suggestion. I got my first set at age 4 (waaaay too late) and was soon covering the entire floor space of my room with giant cities/spaceships/space cities. Things that have a "right answer" (like puzzles and workbooks) are only fun once. Creative stuff like Lego is fun forever.

As for books, why not take her with you to the shop, open a book, hand it to her, and see how she reacts? Or go online and print some stuff at different levels and see how she does with them.