The Prize is my second favorite book of history/non-fiction ever. My favorite is "The Power Broker" which has a similar sort of style and scale. Highly recommended.

Cherokee Tragedy: The Ridge Family and the Decimation of a People by Thurman Wilkins

I actually got into history through visual sources and maps, like Colin McEvedy's "Penguin Atlas of Medieval History." But the history books that I remember really changing my life include Simon Schama's "The Embarrassment of Riches" (a fantastic history of the rise and fall of the Dutch empire), Alfred Crosby's "Ecological Imperialism" (similar to 1491, but more wide-ranging), and Fernand Braudel's Civilization and Capitalism series (the best history books of the 20th century, in my view).

I also remember loving John Brewer's "The Pleasures of the Imagination: English Culture in the 18th Century" and Mario Biagioli's "Galileo Courtier." Also "Mad Blood Stirring" by Edward Muir, which tackles the question of why 16th century Italian street life was so incredibly violent.

Edit: seems apropos to mention that a couple friends of mine are about to launch a site for historians to curate lists of their favorite books on key topics, called Backlist: http://backlist.cc