I guess I've managed to take some of the path you want. My training was as a mathematician but over the last few years I've learnt a lot about theoretical computer science. (I've programmed for many years, but had limited awareness of the existence of theoretical computer science as a field in its own right.)

I mostly learnt from documents available on the web, of which there is no shortage. The exceptions were some parts of [Boolos and Jeffrey](http://www.amazon.com/Computability-Logic-George-S-Boolos/dp/0521701465) for the theory of recursive functions and computability and [Basic Category Theory for Computer Scientists](http://www.amazon.com/Category-Computer-Scientists-Foundations-Computing/dp/0262660717) to help with grasping some of the beautiful connections with category theory. (I know it says "for computer scientists" but I've never met a computer scientist who liked it. On the other hand, I found it very useful as a mathematician.) Years ago, [Cormen et al.](http://www.amazon.com/Introduction-Algorithms-Third-Thomas-Cormen/dp/0262033844) really opened my eyes to the kinds of non-obvious algorithms that exist and shouldn't be hard for a mathematician to read.