Macroeconomic Patterns and Stories, by Ed Leamer. This book, intended as a business school textbook, will familiarize the reader with GDP and the business cycle. It's most valuable insight is considering economics from the perspective of humans as pattern-seeking, story-telling animals.
Last Call: The Rise and Fall of Prohibition, by Dan Okrent.This highly readable account of prohibition shows how regulation of a particular industry can have ripple effects throughout the economy. Readers will also want to familiarize themselves with Bruce Yandle's "Bootleggers and Baptists" theory (wiki, pdf, podcast).
Keep From All Thoughtful Men, by Jim Lacey. Whether you want to understand how economists came to political influence in the Roosevelt administration, where GDP statistics came from, or how economics complemented military strategy during WWII, this is the book for you. Students of economics and military history will both find many useful facts in this book.
See also: Dan Drezner's picks for the topic ten books on global economic history.
Overview: The Strategy of Conflict or Arms and Influence, both by Thomas Schelling. Schelling was the premiere early thinker in the field, and his theories have had a profound influence on almost all the work that followed. His work is also largely non-technical and accessible to general readers.
International conflict: The Clash of Civilizations by Samuel Huntington or Revolution and War by Stephen M. Walt. I wish I could get away without recommending either of these because they are both wrong in important ways, but they are often required reading due to their impact on the field. Take a look at any of various refutations of Huntington's theory after reading his book.
Civil war: Wars, Guns, and Votes by Paul Collier or The Logic of Violence in Civil War by Stathis Kalyvas. Collier is a development economist while Kalyvas is a political scientist, and this shows in their perspectives. These two books complement one another well.
Terrorism: Blood and Rage by Michael Burleigh or Dying to Win by Robert Pape. Burleigh is a historian, and this work builds nicely on his two-volume history of religion-and-politics in Europe. He is strongly opinionated, but the research is solid and the narrative manages to connect accounts of otherwise disparate groups (see also David Rapoport's "four waves" theory of terrorism). Pape is notoriously wrong in many ways but, again, his work is widely read (see this rebuttal).
These readings are roughly in order and build upon one another, but the ones toward the end could be read simultaneously.
Probability and Statistics by DeGroot and Schervish. This book will take the reader from basic understanding of probabilty through linear models. Some of the material may be a review. An understanding of calculus is essential, and linear algebra would be helpful background.
Data Analysis Using Regression and Multilevel/Hierarchical Models by Andrew Gelman and Jennifer Hill. Learning the material in this book will give you a great toolkit, and an understanding of the workhorse models of modern data analysis.
Unifying Political Methodology: The Likelihood Theory of Statistical Inference by Gary King. King's book is useful beyond political science for anyone who wants to understand maximum likelihood estimation. The likelihood theory serves as an important bridge between frequentist and Bayesian methods.
Bayesian Data Analysis by Andrew Gelman, John B. Carlin, Hal S. Stern and Donald B. Rubin. I have not yet read this book in its entirety, but it is a great start. Gelman is a very clear writer, and a great applied Bayesian who does not spend too much time on the philosophy of the method.
A First Course in Bayesian Statistical Methods by Peter D. Hoff. Hoff also has very clear explanations. This book and the Gelman book together make a great introduction to Bayesian statistics. Readers who want a casual history of Bayes' rule should check out The Theory That Would Not Die.