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 for the theory of recursive functions and computability and Basic Category Theory for Computer Scientists 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. really opened my eyes to the kinds of non-obvious algorithms that exist and shouldn't be hard for a mathematician to read.