My two favorite history books are:
Eyewitness to History - It's a collection of hundreds of first-hand accounts of historical events dating back to ancient times. Great reading. This is a great gateway history book, as the variety of topics kind of helps a budding history buff figure out exactly where their interests lie.
A People's History of the United States - It's the history of the US written from the perspective of the losers, so if you were raised in an American public school, there are a lot of new things you will learn.