Others have recommended great languages already, but you also need a good book to teach you not only the syntax and the libraries, but how to think in a different paradigm. So, here are some of my favorites:

Prolog:

• Dennis Merritt: Adventure in Prolog (free!) - the gentlest introduction to a new programming language I've ever seen.
  
• E. Shapiro - L. Sterling: The Art of Prolog (Amazon)
  
  Common Lisp:
  
  
• Paul Graham: On Lisp (free!)
  
• Peter Siebel: Practical Common Lisp (free!)
  
• Peter Norvig: Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp (Amazon)
  
  Scheme:
  
  
• H. Abelson - G. J. Sussman: Structure and Interpretation of Computer Programs (free!) - the classic text; if you read only one book from this list, let it be this one.
  
• D. Friedman - M. Felleisen: The Little Schemer (Amazon)
  
• D. Friedman - M. Felleisen: The Seasoned Schemer (Amazon)
  
  Haskell:
  
  
• B. O'Sullivan - D. Stewart -J. Goerzen: Real World Haskell (free!)
  
• Simon Thompson: Haskell: The Craft of Functional Programming (Amazon)
  
• Paul Hudak: Haskell School of Expression (Amazon)
  
  Enjoy!

The little schemer and the seasoned schemer. They start feeling like a really easy, gentle intro to programming. The dialog presentation style is amusing, and some serious Socratic style teaching going on about programming with an algebraic bent, and the second book builds up to a surprise ending, a rather interesting program -- I won't spoil the surprise for you.

Depends on what you're learning...

I learned how to program basically through these books:

• C# How To Program (I only read like the first 4 or 5 chapters). I don't remember which edition was, but this is a current one => http://www.amazon.com/Visual-2012-How-Program-Deitel/dp/0133379337/ - I stopped because an internet friend of mine told me to read the next one on the list.
  
• The ANSI C Programming Language (aka K&R2). This one is extremely good, but it's harder to read. The problem here is that it's very easy to think you understood the subject while you didn't. It's not focused at teaching people how to program (It's a book on the C language for programmers) although it can be read by beginners. http://www.amazon.com/C-Programming-Language-2nd/dp/0131103628/ - After reading this book for the first time, a guy on the #plan9 irc channel @ irc.freenode.com told me to look for SICP, which I did.
  
• SICP - http://mitpress.mit.edu/sicp/ - Probably the best place to learn programming. The textbook is available online. There are also video lectures from MIT 1985. Reading SICP sorts of open the whole "scheme world," full of pretty interesting materials.
  
• The Little Schemer - http://www.amazon.com/Little-Schemer-Daniel-P-Friedman/dp/0262560992/ - This is a book pretty much on functional programming and specially in recursive thinking. This is the best book on programming I've ever seen. Although it's not a good book to teach you foundations of programming (use SICP for that).
  
• The Seasoned Schemer - http://www.amazon.com/Seasoned-Schemer-Daniel-P-Friedman/dp/026256100X/ - This is kind of a "sequel" to the previous one (same authors iirc). It goes on with techniques for imperative programming. It's really good too.
  
  In between K&R2 and SICP (or was it before the C# book? I don't really remember), I studied some PHP, but it wasn't for long. I've spent considerable time looking at scheme related materials. I really liked many of the books that I've read while "there."
  
  Anyway, these are the books I've studied back when I was starting in the order I've read them. Right after reading SICP, I've re-read K&R2. After finishing The Seasoned Schemer, I read K&R2 a third time. Some years later, I've re-read The Little Schemer, which I intend to re-read again, together with The Seasoned Schemer (they are very good).
  
  Maybe these will work for you, maybe they won't. I don't really know. I can only tell you that I believe they worked for me.
  
  They're not easy books, except for the first maybe. I remember getting stuck fairly often (I was 16 at the time with a poor education background). I just liked doing the exercises/reading the contents so much that I kept going.

The little schemer and later, The seasoned schemer have my highest recommendation.

I think SICP is one of the greatest books I've ever read and that anyone who is serious about programming should read it (or be aware of the ideas discussed there).

However, it is a daunting book especially for newcomers (doubly so if the newcomer wants to get the most out of the book and wants to do every exercise).

I would recommend a book such as Simply Scheme to build up some background knowledge before tackling SICP.

I also highly recommend the Schemer series: Little Schemer, Seasoned Schemer.

Entrepreneur Reading List

1. Disrupted: My Misadventure in the Start-Up Bubble
   
2. The Phoenix Project: A Novel about IT, DevOps, and Helping Your Business Win
   
3. The E-Myth Revisited: Why Most Small Businesses Don't Work and What to Do About It
   
4. The Art of the Start: The Time-Tested, Battle-Hardened Guide for Anyone Starting Anything
   
5. The Four Steps to the Epiphany: Successful Strategies for Products that Win
   
6. Permission Marketing: Turning Strangers into Friends and Friends into Customers
   
7. Ikigai
   
8. Reality Check: The Irreverent Guide to Outsmarting, Outmanaging, and Outmarketing Your Competition
   
9. Bootstrap: Lessons Learned Building a Successful Company from Scratch
   
10. The Marketing Gurus: Lessons from the Best Marketing Books of All Time
    
11. Content Rich: Writing Your Way to Wealth on the Web
    
12. The Web Startup Success Guide
    
13. The Best of Guerrilla Marketing: Guerrilla Marketing Remix
    
14. From Program to Product: Turning Your Code into a Saleable Product
    
15. This Little Program Went to Market: Create, Deploy, Distribute, Market, and Sell Software and More on the Internet at Little or No Cost to You
    
16. The Secrets of Consulting: A Guide to Giving and Getting Advice Successfully
    
17. The Innovator's Solution: Creating and Sustaining Successful Growth
    
18. Startups Open Sourced: Stories to Inspire and Educate
    
19. In Search of Stupidity: Over Twenty Years of High Tech Marketing Disasters
    
20. Do More Faster: TechStars Lessons to Accelerate Your Startup
    
21. Content Rules: How to Create Killer Blogs, Podcasts, Videos, Ebooks, Webinars (and More) That Engage Customers and Ignite Your Business
    
22. Maximum Achievement: Strategies and Skills That Will Unlock Your Hidden Powers to Succeed
    
23. Founders at Work: Stories of Startups' Early Days
    
24. Blue Ocean Strategy: How to Create Uncontested Market Space and Make Competition Irrelevant
    
25. Eric Sink on the Business of Software
    
26. Words that Sell: More than 6000 Entries to Help You Promote Your Products, Services, and Ideas
    
27. Anything You Want
    
28. Crossing the Chasm: Marketing and Selling High-Tech Products to Mainstream Customers
    
29. The Innovator's Dilemma: The Revolutionary Book that Will Change the Way You Do Business
    
30. Tao Te Ching
    
31. Philip & Alex's Guide to Web Publishing
    
32. The Tao of Programming
    
33. Zen and the Art of Motorcycle Maintenance: An Inquiry into Values
    
34. The Inmates Are Running the Asylum: Why High Tech Products Drive Us Crazy and How to Restore the Sanity
    
    

    Computer Science Grad School Reading List
    

    
    

35. All the Mathematics You Missed: But Need to Know for Graduate School
    
36. Introductory Linear Algebra: An Applied First Course
    
37. Introduction to Probability
    
38. The Structure of Scientific Revolutions
    
39. Science in Action: How to Follow Scientists and Engineers Through Society
    
40. Proofs and Refutations: The Logic of Mathematical Discovery
    
41. What Is This Thing Called Science?
    
42. The Art of Computer Programming
    
43. The Little Schemer
    
44. The Seasoned Schemer
    
45. Data Structures Using C and C++
    
46. Algorithms + Data Structures = Programs
    
47. Structure and Interpretation of Computer Programs
    
48. Concepts, Techniques, and Models of Computer Programming
    
49. How to Design Programs: An Introduction to Programming and Computing
    
50. A Science of Operations: Machines, Logic and the Invention of Programming
    
51. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology
    
52. The Computational Beauty of Nature: Computer Explorations of Fractals, Chaos, Complex Systems, and Adaptation
    
53. The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine
    
54. Computability: An Introduction to Recursive Function Theory
    
55. How To Solve It: A New Aspect of Mathematical Method
    
56. Types and Programming Languages
    
57. Computer Algebra and Symbolic Computation: Elementary Algorithms
    
58. Computer Algebra and Symbolic Computation: Mathematical Methods
    
59. Commonsense Reasoning
    
60. Using Language
    
61. Computer Vision
    
62. Alice's Adventures in Wonderland
    
63. Gödel, Escher, Bach: An Eternal Golden Braid
    
    

    Video Game Development Reading List
    

    
    

64. Game Programming Gems - 1 2 3 4 5 6 7
    
65. AI Game Programming Wisdom - 1 2 3 4
    
66. Making Games with Python and Pygame
    
67. Invent Your Own Computer Games With Python
    
68. Bit by Bit

I agree with the recommendations for SICP - it's great.

In addition to the MIT videos, there are videos from Brian Harvey's SICP class at UC Berkeley. They're available both on YouTube and in iTunes.

However, I'll admit that I found SICP a bit overwhelming at first. For context, I'd been programming (primarily Python) for a couple years, but it was my first exposure to Lisp. I ended up taking a brief break from it to work my way through The Little Schemer and The Seasoned Schemer. It only took a week or two and at the end I was much more comfortable diving into SICP.

Not everyone likes the Schemer books - they're quite distinctive - but I loved them. I found them particularly helpful in really groking recursion and continuations.

Some great books for learning Scheme are The Little Schemer and The Seasoned Schemer by Daniel P. Friedman.