Now that Conrad Barski's Land of Lisp has come out (see my review on Slashdot), I definitely think Common Lisp is the best language for anyone to start learning computer programming.
Between Land of Lisp, David Touretzky's Common Lisp: A Gentle Introduction to Symbolic Computation, and Friedman and Felleisen's The Little LISPer, you have three really great books to get started.
Lisp's syntax is a great advantage because it is so simple to learn and has so few special cases. The interactive, iterative development style and real late-binding means you can build programs in parts and add to them as you go. The presence of real metaprogramming means you always have the ability to look at any part of your program and its state to find out what it's doing/what's wrong. The HyperSpec and Common Lisp The Language are two of the best programming language reference manuals ever written.
The best parts about Common Lisp are that it is a language that is hard to outgrow, and that it makes difficult things easy. One of the chapters in Land of Lisp explains HTTP and HTML and has you build a basic web server. That chapter is only 15 pages! There are tons of ideas in the language, and because you are not restricted to a particular programming paradigm, you are always discovering better ways of doing things and developing a personal style.