A recently posted Ask Slashdot: Mathematics Reading List For High School Students? generated a long discussion filled with good (and bad) suggestions. It took a lot of work to read the discussion, so I though it would be useful to make a cheat sheet. Below are all the books--according to my own unscientific survey--that were recommended by at least two people, sorted by the number of recommendations. I probably missed a few as there were dozens of single mentions.
Hofstadter, Douglas R.
Godel, Escher, Bach: An Eternal Golden Braid
Abbott, Edwin A.
Two other books were mentioned as good follow-ups to this book: "Flatterland: Like Flatland, Only More So" by Ian Stewart and "Sphereland: A Fantasy About Curved Spaces and an Expanding Universe" by Dionys Burger, Isaac Asimov, and Cornelie J. Rheinbold. "Flatland" also generated some discussion about whether the author was a sexist and whether it would matter if he were. Someone suggested reading "The Annotated Flatland: A Romance of Many Dimensions" by Ian Stewart to dispel the misconception.
The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography
Singh, Simon & Lynch, John
Fermat's Enigma: The Epic Quest to Solve the World's Greatest Mathematical Problem
Chaos: Making a New Science
Paulos, John Allen
Innumeracy: Mathematical Illiteracy and Its Consequences
How to Lie with Statistics
The Pleasures of Counting
The Feynman Lectures on Physics
Journey through Genius: The Great Theorems of Mathematics
How to Solve It: A New Aspect of Mathematical Method
Bell, E. T.
Men of Mathematics
Levitt, Stephen & Dubner, Stephen
Freakonomics: A Rogue Economist Explores the Hidden Side of Everything
Hardy, G. H
A Mathematician's Apology
Mathematics for the Million
Unknown Quantity: A Real and Imaginary History of Algebra
The Fractal Geometry of Nature
Euclid's Unabridged Elements
Garrity, Thomas A. & Pedersen, Lori
All the Mathematics You Missed But Need to Know for Graduate School
Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics
The Golden Ratio: The Story of PHI, the World's Most Astonishing Number
Surely You're Joking, Mr. Feynman! (Adventures of a Curious Character)
Courant, Richard; Robbins, Herbert & Stewart, Ian
What Is Mathematics? An Elementary Approach to Ideas and Methods
Zero: The Biography of a Dangerous Idea
A Beautiful Mind: The Life of Mathematical Genius and Nobel Laureate John Nash
Kaplan, Ellen & Robert
The Nothing that Is: A Natural History of Zero
The Drunkard's Walk: How Randomness Rules Our Lives
The Man Who Loved Only Numbers: The Story Of Paul Erdos And The Search For Mathematical Truth
Paulos, John Allen
A Mathematician Reads the Newspaper
Tahan, Malba & Baquero, Patricia Reid
The Man Who Counted: A Collection of Mathematical Adventures
God Created the Integers: The Mathematical Breakthroughs that Changed History
Shannon, Claude & Weaver, Warren
The Mathematical Theory of Communication
This book doesn't meet my criteria, since it was only mentioned once, but since I was the mention-er, it earns a special dispensation.