I will recommend "Underground" pretty much unconditionally; it was an amazing read, and I highly recommend it; in many ways it is very much about Japanese society and the repression of history that has occurred many times over; in other ways it very specifically addresses the universal culture of outsiderness, something particularly pertinant in the United States with waco and unabomber etc.
(For those that don't know, "Underground" is about the japanese subway attacks)
I liked Norweigen Wood pretty well, but yeah, wind up bird chronicle is what turned me into an unrepentent Murakami fan. He is also, incidently, a huge music fan.