Computer science for mathematicians This is a big-list community question, so I'm sorry in advance if it is deemed too soft but I haven't seen anything similar yet. 
I've seen computer scientists post questions looking to learn things from pure maths. This is basically the other way around... My ignorance may prevent me from being as specific as I think I would like to be and so I have separated my main question into two.

What good books - readable
  introductions - are there for
  mathematicians to learn about computer
  science?

By this I really mean the science of how computers work. There are perhaps some books out there which are written in a style which mathematicians can relate to - e.g. not practicality-focused, starting from the more abstract fundamentals and building up (I may be wrong but I'm under the impression that a lot of books in other disciplines shy away from presenting things this way around, whereas mathematicians (for better or worse) are accustomed to it). Partly to illustrate what the first question is not asking, the second question is

What good books - readable
  introductions - are there for
  mathematicians looking to learn about
  theoretical computer science, as it is as a
  subfield of maths?

Here is where my ignorance prevents me from explaining the question any more because I can only assume these two aren't the same thing...
It seems quite frustrating that I have made it to grad school and know very little about computers and theoretical CS.
Standard "one recommendation per post" is probably appropriate, + a few sentences about what the books did for you. Also, maybe I should say that I'm not looking to ditch my current interests and become a computer scientist, so things being readable is a fairly strong condition. I'm not looking to become an expert, just to deal with my own ignorance. Thanks in advance.
 A: While I admire both The Art of Computer Programming and Structure and Interpretation of Computer Programs, I thought I'd mention two other books in answer to the first of your two questions. 
J. Glenn Brookshear's Computer Science: An Overview, 10th ed. is intelligently organized and quite well written. It also has worthwhile chapter review problems and useful bibliographies at the end of each chapter.
David J. Eck's The Most Complex Machine: A Survey of Computers and Computing might be worth looking at. If I remember correctly, Eck received his PhD in mathematics from Brandeis University in 1980. 
A: Computer Networks by Andrew S. Tanenbaum is the ideal introduction to computer networks.  We used that book for a one-semester self-study, 
distance education course in Computer Science at the UP Open University.
A: For the second question (theoretical computer science) I strongly recommend Sipser's Introduction to the Theory of Computation.  It is a very easy read for someone with a math background, and requires essentially no specific previous knowledge.  It is essentially a one-semester first course in the subject of computability and complexity theory.  As such, you get all the nice classical results, but not the more recent results which are less complete, polished, or appealing to an outsider who just wants a "taste".
A: I'm surprised nobody has recommended Knuth's The Art of Computer Programming.
A: Well, if you want to know how computers work, the authoritative reference on computer architecture happens to have been written by a set theorist!
John von Neumann. First Draft of a Report on the EDVAC University of Pennsylvania technical report (1945) 101pp.
Ah, the good old days: when logicians understood circuit design and computer scientists believed Rice's Theorem...
A: This question is meaningless if you don't specify the goal(s) you have in mind. Goals are teaching , using , understanding , linking .....
Some people like me think that Knuth is bad from a certain point of view: his writings are interesting, of high quality and contains precise and accurate facts yet it is "not functional" and it is misleading in a way.
As a mathematician try to read some of Wadler below. It is specific but may show you what computing is about. (see https://homepages.inf.ed.ac.uk/wadler/)  .
Computing is about neatly describing parts of the real world, it is not about encoding in zeroes and ones. This confusion is akin to someone saying he 'understood maths' when he has mastered calculus.
A: You could also be interested in the dragon book: "Compilers: principles, techniques, and tools", by Aho, Lam, Sethi and Ullman, which is considered a classic in computer science, from the angle of compilation theory and practice.
A: "Computational Complexity" by Christos Papadimitriou - very good introduction to logic/theory of computation (Turing machines etc.) and computational complexity. One of the best textbooks IMHO.
A: Theory A (Algorithms/Complexity):


*

*Kleinberg, Tardos - Algorithms

*Easley, Kleinberg - Networks Crowds and Markets

*Nisan, Tardos, Vazirani - Algorithmic Game Theory

*Arora, Barak - Computational Complexity: A Modern Approach


Theory B (Logic/Semantics/Automated Reasoning):


*Benjamin Pierce - Types and Programming Languages

*Benjamin Pierce - Software Foundations in Coq (Really lets you see how to translate theory into practice)

*The links here

*Harrison - Practical Logic and Automated Theorem Proving

A: Abelson and Sussman's Structure and Interpretation of Computer Programs is a great introduction (but not a read-before-going-to-bed book, you must do the exercises. This comment applies no matter what book you are learning the subject from).
A: If you want to know how computers work--really work, the the real world--and you have 
some basic understanding of logic design, so you know how elementary gates and latches
are made, and some basic understanding of elementary CPU structure--ALUs, registers,
sequencers and crontrollers--then I think the books by Patterson and Hennessy are tops:  Computer Architectue, A Quantitative Approach and Computer Organization and Design:  The Hardware/Software Interface. They're not terribly mathematical, but they
show, structurally, how modern processors organize, process, and move data.  
If you need the more basic stuff first, there are any number of good introductory texts.
On theoretical side, I would have to agree with John D. Cook that Knuth is the place to go.
(He gives a link in his answer.)  The theory in Knuth is illustrated in terms of realistic
machine architecture--Knuth's MIX computer, for which simulators are available online
if you want to try it out. The model in Knuth is very much a programmer's model--i.e.,
Von Neumann architecture, rather than Turing or state-machine based models such as utilized by
most theoretical computer scientists, but they show how it really looks in practice.
Furthermore, his books are quite sophisticated, mathematically, and certainly propose
some problems which at the time of publication were definitely open and/or research level.
A: For those who want to go from zero knowledge to substantial breadth quickly, I recommend A. K. Dewdney's The New Turing Omnibus.  Once that book is finished, tackling some of the more sophisticated books like Knuth, Aho-Hopcroft-Ullman, and the like seems more reasonable.  Further, the classic books will teach CS theory that is, well, classic, and will leave the reader ill-prepared (in my opinion) for the theoretical and technological developments of this millenium.  The New Turing Omnibus will prepare the reader for classic CS theory, but will not impede those who wish to learn more recent theory.
The book has influenced my writing style.  One project I am working on involves "moving a mountain one pebble at a time", and is inspired by the mountain of a book Dewdney has created.
Gerhard ""Ask Me About System Design" Paseman, 2011.01.05
A: I guess I've managed to take some of the path you want. My training was as a mathematician but over the last few years I've learnt a lot about theoretical computer science. (I've programmed for many years, but had limited awareness of the existence of theoretical computer science as a field in its own right.)
I mostly learnt from documents available on the web, of which there is no shortage. The exceptions were some parts of Boolos and Jeffrey for the theory of recursive functions and computability and Basic Category Theory for Computer Scientists to help with grasping some of the beautiful connections with category theory. (I know it says "for computer scientists" but I've never met a computer scientist who liked it. On the other hand, I found it very useful as a mathematician.) Years ago, Cormen et al. really opened my eyes to the kinds of non-obvious algorithms that exist and shouldn't be hard for a mathematician to read.
A: Although it may not be comprehensive for your purposes, one book that's worth mentioning in this category is Modern Applied Algebra by Garrett Birkhoff and Thomas Bartee.  It's mainly interesting because the theory it presents has a much more algebraic "flavor" than a typical Computer Science treatment of the same material.  There doesn't seem to be a decent preview of the book online, so you may find this AMS review helpful.
A: You don't give any indication of what types of CS you're interested in.
For algorithms, Knuth is classic but old-fashioned; CLRS is pretty standard now I think.
For a connection between CS and logic, you might start with "Proofs and Types" by JY Girard (it's online, http://www.paultaylor.eu/stable/Proofs+Types.html )
Oded Goldreich (http://www.wisdom.weizmann.ac.il/~oded/) has a few books online too.  Lots of good stuff on his site, browse around.  He has some complexity books and an old draft of his "Foundations of Cryptography" that you might like.
Quantum computation: Nielsen and Chuang, Quantum computation and quantum information 
Hang out on some CS blogs, like Scott Aaronson's (which has quieted down lately...).   Look at some of the papers (http://scottaaronson.com/papers/) and articles (http://scottaaronson.com/blog) on his site.
Etc...
A: For your first question, you could have a look at The Elements of Computing Systems, by Nisan and Schocken. It covers the workings of a computer from logic gates, via the CPU to programming languages and the OS.
The website of the book is here; via the 'Study Plan' link you can even find most of the book online, and some presentations based on it - those could be useful to get a quick idea of whether the book is right for you.
A: It's a subset of computer science, certainly, but on the networking front, W.R. Stephens' TCP/IP Illustrated, Vol. 1: The Protocols is a book that deserves a place on everybody's shelf. It's a very hands-on book, including the sources used to actually implement various parts of the TCP/IP stack (from a variety of Unix systems). It also has Fantastically useful diagrams, and makes extensive use of command-line tools to actually test the theory being discussed.
It is certainly the bible for understanding the theory and practice of TCP/IP networking.
