I was going to recommend Alan Booth too.
Some other choices in non-fiction:
'Learning to Bow' by Feiler, a story of his JET experiences. Kind of anecdotal (and occasionally he makes it seem like he was the only person to ever do this, whoo-hoo, when instead there are hundreds of JETs all over the place) but interesting nonetheless.
'The Great Wave', Benfey, a collection of profiles of people who 'opened' up Japan at the beginning of the Meiji period.
Very old and shows it, but fascinating, the turn-of-the-century book 'Japanese Homes' by Edward Morse. This guy travelled all over Japan and made line drawings and wrote descriptions of Japanese houses, recognizing that they were disappearing quickly in the rush to Westernize. Much of it is dry as dust but a lot of it explains much that mystified me about Japanese houses and objects I'd see at flea markets.
'Totto-chan' was recommended to me by a friend but I've never bothered.
'A Boy Called H' was an interesting memoir of a childhood in WWII Japan, though a loooooong book to get through. Also on WWII, an account of Kamikaze pilots 'Blossoms in the Wind' is a revelation of how WWII was presented to the Japanese people (particularly the chapter on the schoolgirls drafted to wait on the military - no, really, all they did was cook, clean and be sweet, but they were totally in the dark about the larger picture)
In fiction:
Oliver Statler's 'The Japanese Inn' is interesting - a fictional account of the life of a Japanese Inn. Reads a bit too much like a textbook at times but it's an engaging way to learn some Japanese history. (the Inn, by the way, no longer exists, I understand)
'The Ginger Tree', a painless way to learn some Asian history, the story of a Scotswoman who goes off to China to marry, and ends up in Japan...it ends just prior to WWII, and is entirely fiction, but very entertaining and a quick read.
'Out' by Natsuo Kirino - creepy! Modern crime and desperate lives.
Murakami is a great favorite of mine but so...strange.
Oh, and the light mysteries of Sujata Massey, which star a young Japanese/American trying to make a living as an antiques dealer in Tokyo while getting all involved in random crimes.
Oh, and last, here's a nice website for a huge list of books on, in, or featuring Japan:
http://www.ohayosensei.com/books/Welcome.html
