One thing I found useful as a self-taught programmer was getting outside of the dominant programming paradigms. Though I'd like to disassociate myself with the over-the-top PG fanboyism that sometimes goes on here, I must admit that his lisp books were a great help in breaking out of the imperative and OO worlds, and were a major influence on me at an early stage.
Even better, PG has now made On Lisp available for free: http://www.paulgraham.com/onlisp.html.