[Book Suggestions] Summer Reading for Younglings.

One for the Morning Glory - John Barnes. Top of my list. Action, adventure, a prince who has lost half of his body, and Highly Unpleasant Things It Is Sometimes Useful To Know.
The Face in the Frost - John Bellairs. Up there with A Wizard of Earthsea for good takes on wizards, and less likely to be found in the course of everyday life.
Speaking of Ursula LeGuin, the first three Earthsea books are a good plan, and I highly recommend Very Far Away from Anywhere Else.
The Phantom Tollbooth - Norton Juster, if she hasn't read it yet, and if the illustrations work correctly on the Kindle.
Has she read The Westing Game - Ellen Raskin? That one's probably in her school library.
Oh, and of course for introductions to SF for someone who likes mysteries, try The Caves of Steel - Asimov.

Related post: On Juvenile Fiction

A Wrinkle in Time and sequels by Madeline L'Engle.

The Caves of Steel by Isaac Asimov. (You said she likes mysteries, right?)

Fablehaven by Brandon Mull.

Anything Tamora Pierce; I'm partial to the Circle of Magic but you could start her in Tortall just as well.

His Dark Materials by Philip Pullman.

Enchanted Forest Chronicles by Patricia C. Wrede.

Ella Enchanted by Gail Carson Levine.

Sophie's World by Jostein Gaarder

Sharon Shinn (not arbitrary books, some of them have a touch of adult content, particularly avoid Wrapt in Crystal and Heart of Gold until she's a bit older; I recommend Archangel in another comment and that's a fine starting point but I think Safe-Keeper's Secret and sequels are best optimized for a kid)

Possibly Zenna Henderson. Mix of fantasy and sci-fi flavors but with a very consistent, distinctive aesthetic throughout; if you like one Zenna Henderson story you'll probably like them all. Vaguely religious sentiments, but coated in enough speculative fiction stuff to be even less problematic than Narnia.

I assume she's already read Harry Potter? That, if not.

Watership Down by Richard Adams is good and is about bunnies. I'm really not sure if I'd classify it as "fantasy". I mean, it's about intelligent bunnies, but they just talk to each other and other animals, they don't communicate with humans or do magic or anything. But it's good.

Michael Ende - Neverending Story and Momo are both available in English.

Avoid Piers Anthony. Piers Anthony exists to be the only available speculative fiction with a kid-accessible writing style in libraries run by people with no taste; saturate her with anything but and perhaps she will never be driven to read his crap.

Be careful - if you try too hard to change her opinions, she might decide Sci-Fi is no good at all. Try to cater to what you know about her interests.

The Scott Westerfeld "Uglies/Pretties" series might be a good introductory book for a girl who isn't interested in sci-fi yet. It has some interesting dystopian implications, but doesn't obviously have the "ALIENS! SPACE!" aesthetic overtones of most sci-fi, which is what turned me off from sci-fi books as a kid.

(I was also mostly into YA fantasy, and didn't like sci-fi until I discovered the part of it that was really about philosophical and ethical questions, not just aliens and space.)

Has she read The Phantom Tollbooth? That's definitely one that's worth checking out. I can never remember what books are at what reading level, but I'm pretty sure it's age appropriate.

Honestly, I've never had a taste for most sci fi either, I've always found it much harder on my suspension of disbelief than fantasy. It's one thing for me to accept a setting that runs on fundamentally different rules, but when a story that's nominally set in our own universe differs from our own in implausible-seeming ways, my instinct is to call bullshit. Sci fi scenarios always set off my implausibility alarms because they weren't weird enough, they're mostly just modern society plus developments in a single metric along a single dimension.

Within YA mysteries, my favorites as a child were The Three Investigators. They had more clever plots than the Hardy Boys and other series, and the protagonists did more actual deduction, observation and reasoning. Also, cameo appearances by Alfred Hitchcock! Sadly, they don't seem to be available for Kindle.

If she hasn't read it yet, you could give her Sherlock Holmes. Quite a lot of (19th century, but still) science and methodic reasoning, should be read before other classical mystery authors like Agatha Christie (because all were reacting to it), and with the bonus (for you) of it being out of copyright and so free for Kindle.

As for SF, how about Jules Verne? It is different enough from current day SF that if she might like it even if she has a prejudice against the latter (no spaceships, aliens, rayguns, etc), but teaches a deeper appreciation for science and scientific progress than most modern SF.

Even as an adult, I enjoyed The Mysterious Benedict Society books by Trenton Lee Stewart. 4th/5th grade is probably about right. How can you not love a series with a book titled The Mysterious Benedict Society and the Prisoner's Dilemma?

I loved these books as an early teen:

Fantasy: The Hobbit (Film coming out in a few months). No hidden pro-science virtues but a lovely, funny book.

Adventure stories:

1. Anything by Jules Verne e.g. Twenty thousand leagues under the sea. Fits into a science-as-exploration theme.
2. Arthur Conan Doyle (The Lost World - a dinosaur book - or some Sherlock Holmes: speckled band, hound of the baskervilles...)
3. Willard Price's adventure series (writing is a bit poor, but that's completely made up for by the exciting-ness and delightful descriptions of wild animals)

Sci-Fi:

1. John Wyndam (E.g Day of the Triffids, The Chrysalids). She may find the post-apocalyptic themes a little distressing though, so that might be a 'for later'.
2. Asimov, I Robot series

Since you said she's interested in fantasy, I'd suggest the Enchanted Forest Chronicles by Patricia C. Wrede (Dealing with Dragons is book one.) Unfortunately it's not on the Kindle yet, but it does a good job of pointing out common fantasy tropes in an entertaining way. Also, the main female character is a very good role model.

If you want more of a scientific mindset applied to fantasy, I'd say The Last of the Really Great Whangdoodles by Julie Andrews Edwards instills scientific curiosity very well. Also not available on Kindle...

Finally, (this time actually on the Kindle!) if you want to gently introduce her to sci-fi while still maintaining fantasy, Diane Duane's Young Wizard series is... decent. Might be a bit scary at parts, though. I don't recommend this as highly as the other two, though. It doesn't necessarily teach anything rationality (although it's been a while since I read it), it's just a good bridge into science fiction.

EDIT: I just thought of a great introduction to non-fiction reading. An Incomplete Education: 3,684 Things You Should Have Learned but Probably Didn't by Judy Jones. It's a general overview of a lot of topics ranging from history to philosophy to science, all in a humorous style. This was one of the books that kickstarted my love of learning when I was thirteen-ish.

I remember enjoying the Prydain Chronicles by Lloyd Alexander when I was at that reading level. It's a lot like Lord of the Rings for children. A Series of Unfortunate Events by Lemony Snicket, Detectives in Togas by Henry Winterfeld.

For sci fi for about that age, maybe Interstellar Pig, although it does not seem to be available on Kindle. Might be a little scary (scared me when I was about that age). Caveat - haven't read it since I was a kid, so not sure how well it holds up.

I enjoyed the Norby series of books, by Asimov and his wife.

How about an anti-birth control story where the third child (In a world where like, you know, only 2 children are normally allowed) becomes trapped naked in a bathroom with a mean bully, so he brutally murders him to escape... then goes on to commit widespread genocide. Young girls love that stuff.

Oh wait, Ender's Game is already on your list. Oops.

Snow Queen by Joan D. Vinge, which won a Hugo Award, is by far the clearest example and best suggestion I can think of, but I'm not seeing it on the Amazon Kindle market. Shucks, what I get for trying to be witty.

I'm surprised HPMOR has not been mentioned yet. It's an astoundingly brilliant piece of fanfiction, and includes most of the themes on Lesswrong, including the philosophies of Rationality and science.

The Giver trilogy is age appropriate and well-written dystopian children's novel. I remember very distinctly that this was my first exposure to what seemed like a plausible future world. (I read this in 4th grade so it might be too easy. )

The Hitchhiker's Guide to the Galaxy would also be good; I read this in 6th grade and it was book that sparked my interest in sci-fi.

The subtle knife series by Philip pullman. Without a doubt

Smith of Wootton Major . I read this book when I was about 10 or 11, and I still remember what it felt like as it rewired my mind.

Ender's Game, of course, as you'd said.

Scott Westerfeld's Leviathan trilogy (not to be confused with that other book by the same title).

Pretty much anything by Terry Pratchett except for The Colour of Magic (it's not great), but especially the Tiffany Aching books (starting with The Wee Free Men), and possibly Small Gods.

Neil Gaiman's Stardust, and especially The Dream Hunters.

The Myth series by Robert Asprin.

Hmm, upon reflecting on this list, I can see that it mostly consists of fantasy. I suspect this is due to my personal bias. I used to read science fiction exclusively when I was little, and there are tons of Russian science fiction writers whom I could recommend, if only your niece spoke Russian, which I suspect she does not. I was not aware that fantasy even existed until the aforementioned rewiring took place.

The Artemis Fowl series should spur an interest in technology - I loved it (I only read up to The Eternity Cube though). The plans in the series also have a lot of flaws, that were frustrating to notice, but I suppose that could provide some lesson or another. It's pretty irrational actually; I suggest it as it may provoke a reaction to irrationality.

Little Brother by Cory Doctorow. It made me really want to learn programming, thought I'm not sure what reading level it is.

The Great Book of Amber by Roger Zelazny should be right up her alley in a couple years.