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.
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.
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.
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.
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).
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.