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...