Stewart, Ian, From Here to Infinity: A Guide to Today's Mathematics. A good overview of modern math, very accessible.
Hofstadter, Douglas, Metamagical Themas:Questing for the Essence of Mind and Pattern. Collection of articles treating subjects from recursion to game theory.
Hofstadter, Douglas, Godel, Escher, Bach: an Eternal Golden Braid. Strange loops and strange isomorphisms (in a loose sense of the word) between music, biology, logic, computers, and other similar stuff. Won the Pulitzer Prize.A review from Meep
Conway and Guy, The Book of Numbers
Gardner, Martin, Any of his math books. They're all great.
Ball and Coxeter, Mathematical Recreations and Essays.
Stewart, Ian, Game, Set and Math: Enigmas and Conundrums.
Dunham, W., Journey Through Genius.
Dunham, W., The Mathematical Universe.
Stillwell, Mathematics and Its History.
Hardy, A Mathematician's Apology.
Stewart, Ian, Does God Play Dice?On nonlinear dynamics (more infamously known as chaos theory) and other things. Very accessible, no equations, doesn't really tell you how to compute these things.
Graham, Knuth, and Patashnik, Concrete Mathematics. And you thought Fermat wrote hot marginalia... A review by Meep
Wilf, generatingfunctionality. Also available online at http://www.cis.upenn.edu/~wilf/. Cool book as well, but harder than GKP's
Korner, Tom, Pleasures of Counting.
Koh and Chen, Principles and Techniques in Combinatorics.
Cameron, Peter J., Combinatorics. A harder textbook, but with interesting material on many different branches of combinatoric, including design theory, generating functions, coding theory and graph theory.
Scarne, John,Scarne's New Complete Guide to Gambling. Even though it was written in 1974, the principles are still the same. Don't try Martingale betting!
Mosteller, Frederick,Fifty Challenging Problems in Probability. A Dover book (cheap!!) with archetypal problems. Also a review by Meep
Weaver, Warren, Lady Luck: the Theory of Probability.
Mero, Laszlo, Moral Calculations: Game Theory, Logic and Human Frailty. Terrific book, accessible, but do not, under any circumstances, attempt the Dollar Auction. Also, a review from Meep
Stahl, Saul, A Gentle Introduction to Game Theory. American Mathematical Society. Shows you how to calculate most things of interest for simple games. Also, a review from Meep
Schneier, Bruce, Applied cryptography: Protocols, Algorithms, and Source Code in C. A big thick book, but easy to read with little difficult mathematics. Lots of references, and a very solid description of the basics of the subject.
Adams, Colin C., The Knot Book: An Elementary Introduction to the Mathematical Theory of Knots. It has a section of jokes at the back, which every math book should have.
Churchill, Brown and Vehey, Functions of a Complex Variable.
Straub's Outline for Complex Variables.
Nehari, Zeev, Conformal Mapping.
Conway, John B., Functions of One Complex Variable. From Meep -- There's a proof in here with the punchline 1/72 that just killed my intro class. It was the funniest thing we heard all semester. You just had to be there.
Beardon, Alan, Complex Analysis: the Argument Principle in Analysis and Topology. Out of print, but worth tracking down from a library.
Gelbaun and Olmsted, Counterexamples in Analysis. Wild n woolly functions -- find out that you really have no good idea of what a continuous function looks like.
Oxtoby, Measure and Category. It's a graduate text, so it's difficult to read.
Korner, Tom, Fourier Analysis. There's also a companion "Exercises on Fourier Analysis".
Bartle and Sherbert, Introduction to Real Analysis. People in the epsilon-delta class: this is the textbook with the K-epsilon game.
Cofman, Judita, What to Solve? Problems and Suggestions for Young Mathematicians.
Polya, How to Solve It: A New Aspect of Mathematical Method.
Larson, Loren, Problem-solving Through Problems.
Gilbert, Larson and Krusemeyer (That's Mark!), The Wohascum County Problem Book.
Shklarsky, et.al., The USSR Olympiad Problem Book: Selected Problems and Theorems of Elementary Mathematics.
Yaglom and Yaglom, Challenging Mathematical Problems with Elementary Solutions, vol. 1.
Holton, Derek, Let's Solve Some Math Problems.
Gardiner, Anthony, The Mathematical Olympiad Handbook: an Introduction to Problem Solving Based on the First 32 British Mathematical Olympiads 1965-1996. Nice book, providing a brief introduction with some methods, and giving hints to most of the problems, in addition to full solutions.
Garnier and Taylor, 100% Mathematical Proof. Good intro to logic in math proofs and simple proof techniques. If you're shaky on how to prove things rigorously through logic, this is a good place to start.
Solow, Daniel, How to Read an Do Proofs.
Polya, Mathematics and Plausible Reasoning. A somewhat more difficult book on logic and proofs.
Smullyan, R., Any of his books. If you're really into insane and sane liars and truthtellers, he's your man.
Games Magazine or Games World of Puzzles, Paint by Numbers. The cutest logic puzzles one ever did see. Interestingly, the two-color puzzles are easier than the one-color ones (once you get the hang of things).
Dudley, U., Mathematical Cranks. Some of this is very funny indeed.
Dudley, U., 200% of Nothing. The very unfunny way math is misrepresented in real life.
Huff, D., How to Lie with Statistics. An old book, but much of what is described inside still goes on with reporting of statistics. You need the standard deviation! Review by Meep
Gardner, Martin, Gotcha!. Easy to read, and contains descriptions of many important paradoxes.
Barwise and Etchemendy, The Liar: An Essay on Truth and Circularity. Much more advanced book dealing with Russell's paradox (the Liar...used in diagonal arguments).
Stalker, D., ed., Grue!. Collection of articles on Hempel's paradox -- a paradox of scientific (as opposed to mathematical) induction. Rather difficult.
Burger, Dionys, Sphereland. And those Victorians thought Flatland was wild...
Gamow, George, Mr. Thompkins in Paperback. See what happens when you have quantum effects on pool tables or the speed of light is 65 mph (no more need for state troopers!)
Herbert, Nick, Quantum Reality: Beyond the New Physics. Extremely easy to read for metaphysics.
Feynman, Richard, The Character of Physical Law. For the man on the street.
Rucker, Rudy, The 4th Dimension. I can see it! I can really see it!
Donald E. Knuth, The TeXbook. A dense, but definitive, description of the TeX system. One of the best descriptions of typesetting mathematics in TeX available.
Helmut Kopka and Patrick W. Daly, A Guide to LaTeX: Document Preparation for Beginners and Advanced Users (3rd ed.). A very nice book describing the standard LaTeX macro package; this is used by almost everyone. A much easier read than Knuth, but if you want to advanced things, you'll need the TeXbook. The coverage of typesetting math is much more basic than in The TeXbook as well.
The TeX Users' Group. This has links to all sorts of useful information, such as where you can get a working TeX system for your machine. There are both free and commercial implementations available for most platforms; TeX and LaTeX themselves are free.