The Art of Computer Programming, Volume 1: Fundamental Algorithms

Knuth, vol. 1.

I was about 17 when I encountered The Hacker's Dictionary. It hasn't been updated much for years, but I think it would still provide an easy-to-read gateway into the way programmers think and some interesting tidbits of history. Reading or watching Guy Steele's Growing a Language talk could be fun. The Little Schemer could be a good choice. Van der Linden's Expert C Programming covers some serious C topics, but is also generally educational and enjoyable. You could introduce them to Knuth's writings in an easily-digestible way, like maybe having them read and implement the Easter date algorithm in Volume 1. Maybe have them read [excerpts from?] something like Philip and Alex's Guide to Web Publishing and put together a small database web application.