First off, there isn't much difference between C and C++ for the basic operations and thus not much difference for the beginning programmer. The real value of C++ lies in memory management in classes, the STL and other advanced features which you really will not be using the first months or so.
Second, C is (nearly) a perfect subset of C++, so it's not like learning two distinct languages. Do note that correct C++ programming is not at all like compiling C with a C++ compiler.
Concrete, solid advice would be to start with K&R and, if you're interested in C++, move on to the C++ Annotations. The last URL is an entire bookwork on correct C++ programming for people moving over from C (or even Java).
Of course, if you want to get started on C++ right away and 'skip' C, the The C++ Programming Language is the place to start.
On a general note, I do not agree with some things being said here, specifically regarding to the rigidity of C vs. C++. C++ is much stricter and will not allow you to do many things due to is very strict typechecking. C++ can be used more safely than C by casting, hiding your data, etc. But you will have to do it. It's not inherent to any languge that you always use it correctly. 
Also, C and C++ have roughly the same syntax (barring some C++-specific constructs) and it would be mistake to say C++ is complex due to its syntax. The complexity of C++ (vs. C) is due to its massive semantics.
Lastly, I do not agree with the idea that C++ is somehow more bloated than C or that it only has real value in larger, more complex programs, but these sort of statements can be argued about forever.