For a layman, any recommendations of a "CS 101" book would be greatly appreciated.
For an intelligent layman, Structure and Interpretation of Computer Programs.
By far the best intro book, that will make sure you start in the right direction (mentally)
Then pick your flavor (head first keeps it at a high level): Java C#
There are lots of great "CS 101" type books out there, but many of them approach things differently, so it really depends on what your goals are. While I agree with Skilldrick that SICP is a great book, it is also very "academic" in its approach. That is fine if it is what you are looking for, but maybe not so good if you are looking for a more mainstream programming approach. I would recommend checking out one of these:
Practical Programming: An Introduction to Computer Science Using Python
Python Programming: An Introduction to Computer Science 2nd Edition
"The best book on programming for the layman is Alice in Wonderland, but that's because it's the best book on anything for the layman."
Alan Perlis, "Epigrams on Programming"
Very good for learning to program in a very readable language is Learn to Program. For a generic CS book I agree with Nix that you can't go wrong with The Pragmatic Programmer.