Ferris, Timothy. The Whole Shebang: A State-of-the-Universe(s) Report. New York: Simon & Schuster, 1997. (This book by Ferris does not have the historical and philosophical material of Milky Way, but it does give a good update, especially if you like Ferris' writing.)
Greene, Brian. The Elegant Universe. New York: W. W. Norton & Co, 1999. (I believe this is Greene's first book, but it was extremely successful and was made into a PBS miniseries which you can watch online here. This was the most exciting physics book I had read in many years.)
Greene, Brian. The Fabric of the Cosmos: Space, Time, and the Texture of Reality. New York: Knopf, 2004. (Green's second book, which, in my opinion, cements his position as Sagan's successor as the popularizer of physical science. This book has a wider scope than Elegant Universe and might even be read before it. If possible, it is even better than Elegant Universe and gives a superb review of all physics leading to the question of the nature of reality and the universe. This is the most exciting physics book I have read since Elegant Universe.)
Hawking, Stephen W. A Brief History of Time: From the Big Bang to Black Holes. New York: Bantam, 1988. (Carl Sagan wrote the introduction. This used to be our text for Honors Physics. Hawking has other good books too, such as Black Holes and Baby Universes, and The Universe in a Nutshell.)
Hofstadter, Douglas R. Godel, Escher, Bach: An Eternal Golden Braid. New York: Vintage Books, 1980. (This book ties art (Escher) and music (Bach) with startling theorems of math (Godel) and computability. A tour de force. One of my favorite books. From the cover: "Every few decades an unknown author brings out a book of such depth, clarity, range, wit, beauty, and originality that it is recognized at once as a major literary event. [This] is such a work." Martin Gardner.)
Sobel, Dava, and William J. H. Andrews The Illustrated Longitude. New York: Walker Publishing, 1998. (This is the story of how John Harrison won the prize in the race to determine longitude. More info is available here.)
Hirshfeld, Alan W. Parallax: The Race to Measure the Cosmos. New York: Henry Holt and Company, 2001. (This is the story of how we learned to measure parallax, and thereby the size of the universe. This measurement is part of coming of age.)