History isn't taught till middle school?!? Presumably the schools would claim they teach history in an integrated way, combined with other subjects, not that they don't teach it at all?
My 2pworth is that though narrative is great, a gifted 4th grader is likely to be able to cope with more than just narrative - I'm very uncomfortable with the SotW approach because it (apparently) doesn't really do history beyond stories. The most interesting part of history is the evidence and its interpretation!
A general point, then, is that you might consider books written for UK schools, because history here is evidential from the start. For example,
So you really want to learn History is supposed to be good, though it's English history. (Key Stage 3 begins at age 11, fwiw.)
Not a book, but have you considered the Great Courses? We all very much enjoyed Bob Brier's
History of Ancient Egypt when DS was about that age. He also has shorter courses there on Egypt, and has written several books, though I haven't seen any of them.
