I recently picked up a copy of Introduction to Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography, by Juraj Hromkovič. (Spriger, EATCS series)
I thought the chapters in the book were pretty introductory, however the emphasis here was on mathematical (and formal) rigor. There were no intuition-based talks, but everything followed from deductions. The book is very conservative about notations and formalism, which i think is a good thing, especially for new researchers (like me)
The nine chapters covered a lot of ground, and would benefit anyone who wants an introduction to the topics listed in the cover. Although, they were mostly introductory, it still conveyed some of the important ideas in the topics and in Theoretical Computer Science in general. I particularly enjoyed the read on Kolmogorov complexity.
The book, I felt, is accessible to an advanced undergraduate, or anyone with a enough mathematical maturity. There are some really nice exercises as well, and it can be fun to discuss those. The exercises were mostly based on the ideas that came from the sections that preceded it.
Overall, anyone who wants to explore CS Theory to a level of attending a talk in a Theory conference, can take a look at this book, the exercises require some work, but i won’t say they are really challenging.