Read Brian Greene's The Elegant Universe, and then watch the Nova program based on the book that aired on PBS. Although a few years old, most of what it says remains accurate. Also read his more recent book The Fabric of the Cosmos written in 2004.
Black Holes and Time Warps: Einstein's Outrageous Legacy by Kip Thorne. Everything from Einstein to Hawking and beyond. Relativity, and how it must be reconciled with quantum mechanics to achieve a true understanding of the Universe. He also goes beyond to some very speculative physics relating to time warps and worm holes, although both of these ideas do have a basis in relativity theory. Includes a number of personal anecdotes which I feel add to the book; some people, I know, disagree.
Lee Smolin's book Three Roads to Quantum Gravity explores String Theory, "M" Theory and Loop Quantum Gravity (LQG). It proposes that all three are approximations to a single underlying theory. An interesting man, he gets very frustrated that String and "M" theory get by far the largest share of particle physics research, and that his pet theory (LQG) gets very little, as discussed in another of his books The Trouble with Physics, which I would not particularly recommend.
Michio Kaku is a well known populariser of science, and all of his books are a good read. I particularly like Hyperspace: A Scientific Odyssey Through Parallel Universes, Time Warps, and the Tenth Dimension. It is another book that addresses the reconciliation of Relativity and Quantum Mechanics, and is one of the best at explaining the "how" and "why" of multi-dimensional space; for example why String Theory is formulated in ten dimensions.
John Gribbin's 1984 book In Search of Schrödinger's Cat: Quantum Physics And Reality is the best introduction to the whole of quantum physics. While it does not cover some of the latest discoveries, like quantum entanglement, all the basic necessities are there. Cosmic Coincidences: Dark Matter, Mankind, and Anthropic Cosmology, written in 1989 with Martin Rees, now Astronomer Royal in the UK, is also quite interesting as an introduction to the Anthropic Principle. It is a very well written book, containing a wealth of information. Personally, I see very little relevance in the anthropic principle; you may disagree.
Lisa Randall's book Warped Passages: Unraveling the Universe's Hidden Dimensions, published in 2005. Where most multi-dimension proposals posit microscopic extra dimensions, possibly on the Planck length scale, she proposes large, possibly infinite extra dimensions. These ideas may explain why gravity is so weak compared to electromagnetism and the other forces of nature. In reality, the subject matter is complex and heavily mathematical, but her use of allegory makes getting to the core of what she is saying logical and fun. Also, for the first time, we have a theory that could be explored experimentally once the LHC is up and running. Jolly good read.