As for non-fiction, I prefer history, so here are a few recommendations:
John Keegan: A History of Warfare and The Face of Battle. Also The Mask of Command, The Price of Admiralty, Six Armies in Normandy, The Second World War, and The First World War for people who can’t get enough military history.
Jared Diamond: Guns, Germs, and Steel.
Barbara Tuchman: A Distant Mirror, The Proud Tower. I would recommend The Guns of August but I prefer the analysis of the beginnings of the First World War in Keegan and in
Donald Kagan: On the Origins of War.
Paul Johnson: A History of the American People, A History of the Jews, Modern Times.
Robert Hughes: Barcelona, The Fatal Shore.
Hugh Thomas: The Slave Trade, The Spanish Civil War.
David McCullough: The Path Between the Seas.
William Manchester: American Caesar.
Books I liked but that I don’t remember the authors of because I don’t have them: Plagues and Peoples, Hitler’s Willing Executioners, The Promised Land, Peter the Great.
Historical novels I liked: Charles Frazier, Cold Mountain; MacKinlay Kantor, Andersonville; Robert Penn Warren, All the King’s Men; Gore Vidal, Lincoln; Robert Graves, I, Claudius and Claudius the God; John dos Passos, the U.S.A. trilogy.
For interesting what-if history, try Niall Ferguson (ed.), Virtual History.