The best (deepest, most material, most elegant) computer science textbook is Structure and Interpretation of Computer Programs , by Abelson, Sussman, and Sussman. It's a hard book to get through, though. Somewhat easier, but in the same spirit is the new book How to Design Programs .
Neither of these books is really aimed at students who want to program because it's fun or because they have something small they want to do. They're really aimed at future professional software developers. The best books aimed at the less-hardcore user are by Brian Harvey. His book Simply Scheme uses the same programming language as the earlier two, Scheme, but is more approachable. My favorite of this class of books, though, is Brian's three-volume set Computer Science Logo Style , which combines good computer science with creative and fun projects.