I'm pretty sure I would fall in the "crossword fanatic" category. There's a handful of them available, most for free, but there is one in-particular that stands out.
Having tried them all, my favorite by far, over the paid-app Crosswords, is the free Crossword Lite. It comes with four sets of 50 puzzles for a total of 200. The individual sets are displayed on the very first page and informs you how many have been started (and not) as well as completion.
For usability and functionality, you can use portrait for a full screen puzzle or landscape if you prefer seeing the list (to the right). There is no difficulty setting to choose from, greatly diversifying the puzzles. Under options, you also receive a clue list, the ability to check answers (You have X correct words, there are X left to solve, X are wrong - show errors?), as well as a means of cheating when stumped (reveal answers).
Performance-wise, all of them I tried have been flawless on the Fire.
There are also tons of other mentally-challenging games available. She will love her Fire!