I'm about to start my second year of a bachelor's degree in pure math. I've taken upper-division linear algebra, complex analysis, and point-set topology, as well as the calculus sequence and ODEs. Next year I'm taking abstract algebra and real analysis (although I already know some group theory and a fair bit of what'll be taught in my intro real analysis course, through self-study). As for CS, I have experience writing code, but not much knowledge of the theoretical aspects.
Enough about my background, now onto my interests.
I'm interested in learning about the theoretical side of computer science, by which I mean that branch of computer science which is also a branch of pure math. I find everything from Turing machines to algorithmic complexity theory fascinating, but math is pretty much impossible to learn by browsing interesting Wikipedia pages, which is why a book is needed!
My criteria for a good math book include rigor (precisely-stated definitions and theorems, and correct proofs) and exposition (motivation for results, clarity of proofs, and so on). Can anyone recommend some books about the mathy aspects of CS that would be understandable at my level of preparation?