I wish someone had told me about this book when I was younger: A.I. Mal'cev, Algorithms and Recursive Functions.

The exposition is simple, thought provoking and rigorous. You are teased to delve into many strains when reading it.