For someone just getting started in Computer Science I would recommend
Douglas Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, 1979.
It is a philosophy book discussing the meaning of truth, proof, and computability, (and self referential music and art and ... a bunch of other stuff) aimed at people with a little bit of mathematical sophistication (say at least a semester of college calculus) and was the book that inspired me to study computer science. It walks the reader through a complete proof of Gödel's incompleteness theorem.
I know I am going to get downvotes from the theorists for this, but I actually think that the first few chapters of most books on compilers do the best job of introducing basic automata theory (regular and context free languages, finite and pushdown automata). Aho, Sethi and Ullman (the red dragon book) does a particularly good job, but Appel's Modern Compiler Implementation in ML/Java/C book is decent and Cooper and Torczon's Engineering a Compiler is also great. The mathematics won't be particularly rigorous but the point is to get you to understand how to actually use and implement these things in real life. They won't teach you about Turing Machines, computability or decidability though.
The best book, the one that should be at the core of learning automata and computability, and the classic in this field for 20 years was
John E Hopcroft and Jeffrey D Ullman, Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 1979.
Sometimes known as "the loom book" because of the strange cartoon on the cover. It is appropriate for 4th year undergraduates or 1st year graduate students in computer science. It covers automata theory and computability. (It also ends with a couple of chapters on complexity theory, but that's not really its focus.) In about 2001 Addison Wesley started to "churn" the book (releasing new editions with modifications to kill the used book market.) I haven't looked at the 2nd (2001) or 3rd (2007) editions that added Rajeev Motwani as an author, so can't tell how or if they are improved over the original 1979 edition.
The book discussed in Stephen Bly's answer
Michael Sipser, Introduction to the Theory of Computation, Thompson, 1996 (now in 3rd edition, Cenage Leraning, 2012.)
is truly excellent. It is easier to read than Hopcroft and Ullman. Sipser is a good writer and explains everything extremely well. It doesn't go into the depth and range of topics that Hopcroft and Ullman, so may not include enough for a graduate course focused on automata and computability. Sipser is about 1/2 automata and computability and the other half is complexity theory (which he covers in more depth than Hopcroft and Ullman's first edition did.)
For a student who is taking a course in computability I recommend they read the following when they need to relax:
Raymond M Smullyan, The Lady or the Tiger?: and Other Logic Puzzles, 1982 (Dover reprint, 2009)
which ends with a series of chapters that requires you to do an undecidability proof to solve the puzzle.
Once you've got a good background on computability, you might like to continue on with a deeper look into other aspects of mathematical logic (including a rigorous treatment of Gödel's completeness and incompleteness theorems.) A good book for that might be
Herbert B Enderton, A Mathematical Introduction to Logic, 2/e, Academic Press, 2001.