I don't agree with most of the recommendations above. Mixing semantics as happens in a lot of modern programming languages is not good for learning: pointer vs. copy passing as in primitive types vs. objects etc. Floating point vs. integer arithmetic with its automatic conversions ...
When learning to program, there are 2 totally different things to learn:
1. clearly structuring a problem
2. the nitty gritty messy stuff: pointers, floating point number issues (rounding), communication with hardware (I/O),
A language like Pascal (if you have a dialect with supports pointer dereferencing (original pascal only made this possible via var-parameter passing) forces one to structure the problem, has very strict semantics and still lets one learn the complexity of pointers and the essential data structures: trees, lists ...
Complement it with structured programming and stepwise refinement (Dijkstra) to learn to structure problems.
Once one masters all this, it becomes a piece of cake to write a well-structured C program, and picking up on all the additional nitty gritty stuff that C doesn't hide.
With ADT (abstract data type) based programming in Pascal, one approaches OO programming, and the step to OO-pascal or C++ can then be made.
A great language for learning how to structure a problem is a functional language like Haskell. Strongly typed, lazy evaluation, support for unlimited lists etc. Based on lambda-calculus, hence with strict semantics.
Sorry, but have no book recommendations at hand.