List of intro TCS books for those who don't know much about TCS
If you would like to have a general introduction without getting to deep into the technical details, I suggest David Harel's Algorithmics: The Spirit of Computing. After that, this is my favorite list:


Michael Sipser's Introduction to the Theory of Computation: the best introduction to automata theory, computability and complexity.
Algorithms by  S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani: the most intuitive introduction to algorithms with stronger focus on intuition than technical proofs.
Jon Bentley's Programming Pearls: this is not a textbook on algorithms, but it demonstrates beautifully how to use algorithm design techniques to solve real problems that irritated real programmers. :-) This might be a good start if you have some pre-knowledge on programming.