I'm currently studying Java at the university, and after having been highly sceptical of it I must admit it is a very versatile language.
All programs you create will be able to work on any system that that the JVM is available on, it's quite intuitive and not too hard to get into.
I would not learn C first.
This is because, as Phantasm says, Java and C++ (and C# (if one can call that a language on it's own)) is an Object-Oriented Programming language (OOP) and thus has a radicly different approach on how to do things.
While learning C would teach you a lot you might/will use later, it would also mean learning an "outdated" programming "thinking" and then OOP.
(I had a hard time going from VB to Java, and VB is a much more OOP than C will ever be)
Why learn Java instead of C++?
Java will work on any system with a JVM on it, whereas in C++ you'll have to change your code to port from one platform to another.
Java is a language which is very much oriented towards Distributed Computing, with class libraries to get everything set up easily.
Java is a powerful language who's programs can either be run as stand-alone programs, or (with very little modification) be run in a web-browser
And lastly, Java is becoming (if it has not allready) the defacto language at universities. Thus if you learn Java, a degree could be within your grasp
No matter if you choose Java or C++, they're quite similar languages (with Java being based on C++) so it won't be too hard to learn one if you know the other.
When it comes to what book to use to learn programming, I have a couple of suggestions.
For C++ I've found "C++ A Beginners Guide" by "Schildt" from "Osborn publishing" to present everything in an easily grasped way. (But read in it a bit before you buy it make sure you feel the same)
For Java, I don't have a book I can recommend (although Schildt has written a book about Java too). But I have a couple I can warn you about.
Do not buy JavaGently 2ed. It is absolute crap, and should never have existed!
3rd edition is ok, but has one great let-down. It uses special classes to teach you.
When getting a book to learn programming, I highly suggest staying away from the books that uses special classes to make it easier for you. Especially if they use it for more than reading from keyboard/file and to file/screen, but also for GUI programming etc.
The reason I say this is that after you've done learning those special classes, you have to learn what Java really uses.
Yes, Java's standard might be a bit hairy in the read/write op I listed above, but you won't be finding yourself coding with commands no-one but those who's read the book know about.
If you're on the University, it's another matter again, as there you will learn the "real" way of doing it too, they're only "dumbing it down" for the first few courses.
One last thing when it comes to which book to buy. Buy a highly rated, but "slim" (5-600 pages) book.
You don't need a bible to get started in programming, and getting one will only frustrate you until you know enough to make sense of it.
Check out what is recommended at Amazon.com, then go to a regular bookstore and read a bit in the book.
If you get a book with high ratings, but you can't understand/don't like the approach it's worthless!
Also making sure you get a good book you understand will make learning the language eaiser (as you won't sit there wondering what the h... is going on as I did with Java Gently 2ed).
Hope this helps you in choosing language and book