Summary
Programming is a passion for you: Do learn C, and as soon as possible, move to another, more complex languages (C++, Java, C#).
Programming will be your job, but you'd rather do anything else than play with compilers at home: Do learn Java. Some low level understanding will be missing, but hey, no one needs knowing how a car really works to use it as part of his job.
Why C would be a good/bad idea?
C is very low level, but not too much. You have variables, functions, a stack and a heap. You'll have pointers, dynamic allocation and, some C glitches are interesting to know if you want to have some edge over other developers.
But C breeds bad habits. For one, it breeds arrogance. Nothing is so much nerve-wrenching and at the some time amusing than a C developer trying to tell you how much his language is better than yours, because it is faster (usually a lie), and better (lie, again). With C, (as with C++), standard libraries are so poor it is an eternal source of frustration (of course, there are a lot of libraries around the web, but then, they're out of the standard...). Despite what is promised elsewhere, C won't give you all the basics about programming. Its object-oriented features are non-existent, and if you stick too much to it, you'll fossilize your mind and everything you'll learn will be criticized about how you could do it in C, instead of what this new way of thinking to make your programming experience richer.
Conclusion: Do C only to learn from it. Do not keep yourself constrained to C. Either move to C++, as C++ can be a low level as C, and can be almost as high level as C# or Java. Or go even further, and move to C# or Java.
Why Java would be a good/bad idea?
Despite what some people would tell you, despite its higher language status, Java (or C#, for they are of the same language family) is quite efficient, and now are able to reach efficiency level of C/C++ in code execution. It is object oriented, and its libraries are so complete it'll just blow your head off (don't be intimidated, though). For the average developer, it is more "cross platform" than C or C++ because its standard library is present on any Java Runtime. So, if you do a C GUI program on Linux, and want to see it executed on Windows, you'll have to learn some tricks (I did not have the patience). For Java, just copy your jar files on any computer with a JVM, et voila.
Now, Java is no silver bullet. Sometimes, it can just be slow, and some processing will have to be done in C or C++ through JNI bindings. And if Java will teach a lot about statically typed object oriented programming, it will do little to teach you about low level programming, pointers, memory, etc.. It's difficult to explain, but, as a C/C++ programmer, I like to see a Java or C# program and instinctively know what processing will be slow, and what will be fast. It's pleasing to start my first brush of C# with ".NET/C# optimization" and understand a digest easily everything explained there. This is the kind of feeling someone who started with Java, C# or (gods help them) Visual Basic can't ever start to perceive.
Conclusion: By going straight to Java, you'll avoid some chores from C. The problem is that some knowledge lost among this low-level language will perhaps be missing when you need them.
So what?
For now, from what I perceive around me, the mainstream programming is done using C++, Java and C#, C++ losing its edge as easier programming languages reaches its speed (JIT is just marvellous). So, by the time you'll be searching a job, perhaps C++ will be outdated (or not... We'll see if C++0x will keep its promises).
My take: If you're the kind of people who like programming, and would do it on their own time, for pleasure, then do C, and then move to C++, Java and C#. If for you, programming is just a job, and the idea of trying this new feature or new language is kinda alien for you, move to the practical, and learn Java and stick to it.