First off, absolutely get a copy of _Structure and Interpretation of Computer Programs_ (SICP: http://mitpress.mit.edu/sicp/) - this is one of the best books on programming I've ever seen, and while it uses a subset of Scheme, it's really more about major concepts in CS. It's excellent. Do the exercises. It will take a while, but do the exercises.
For C, get _The ANSI C Programming Language_ by Kernighan and Ritchie ("K&R"). Harbison's _C: A Reference Manual_ is a good reference.
If you do real work in C, you might find Lua helpful - it's a C library that provides a drop-in scripting language for C projects. It's a also nice language in its own right, simple but very expressive, and stylistically somewhere between Python and Javascript. (_Programming in Lua_ by Ierusalimschy is the only book you need, though having a printed copy of the reference manual wouldn't hurt.)
Prolog is a fun language. You'll probably need to stick with it a while before it switches from being weird and novel to actually useful, though, and be prepared to be a little disappointed upfront - some of the early AI hype oversold it. It's actually pretty lousy as a theorem prover, but it has a unique programming model that is very powerful for some problems. (It will also help if you want to learn Erlang later.)
For Prolog, I like _The Art of Prolog_ by Sterling and Shapiro. It's on logic & declarative programming as a paradigm, and how well Prolog lives up to it. It's deep, and uses Prolog to teach about programming in general, much like SICP does with Scheme. Highly recommended, whether or not you use Prolog in the long run. (The newest edition is kind of expensive, but you could get by with the first edition. They fleshed out the latter 'project' chapters a lot in the second, though.)
As a reference, _Programming in Prolog_ by Clocksin & Mellish is good. I also liked _Clause & Effect_ by Clocksin; it's sort of like _The Little Schemer_, but for Prolog. _The Craft of Prolog_ by O'Keefe is great, once you're comfortable with the ideas in _The Art of Prolog_.
The thing that made data structures really make sense to me was learning OCaml. (_Developing Applications with Objective Caml_ is free online: http://caml.inria.fr/pub/docs/oreilly-book/) Having a garbage collector helps, and the ML family has powerful tools built-in for working with types and data structures. Doing the exercises for the first three or four chapters of that book is enough, if you're only going to use it to study data structures. (It's a great language, too, though.)
Edit: Added Lua subsection to C.
So when we later got to C, the new things were the syntax and the imperative model, but most students had learned enough about algorithms to know what they wanted to do, which made it a lot easier to learn.
After that we also tried out Prolog, which belongs to yet another paradigm, so over the first year we tried a variety of languages that got you thinking very differently about programming than if you'd only do an imperative language.
Later on in the program we had some courses that went down closer to hardware, we did assembly language, and we even wired our own processor, did the microcode for it, and wrote a small assembly program for the "computer" we made.
Over the course of the entire program we never dug deep into one specific language or paradigm, but we went across the entire field of computer science, and that turned out to be an excellent foundation. In my experience, the people I know that are really good programmers have all done this, either through university, or by self-study. It requires a lot of passion for programming to do it by yourself though, but it's an alternative to finding a diverse CS program that focuses on breadth instead of depth.