In my opinion the goal of teaching the first language to students is to enable them to think in an algorithmic way. It should make as simple as possible to grasp such basic concepts as recursion, iteration, computational complexity, recursive data structures and so on. Encourage them to write beautiful code and elegant algorithms rather than super eficient code that takes advantage of all the quirks of the architecture. Essentially, this means not getting in the way of the student. The practical stuff should come later, when the students already understand what they are trading for better performance.
This means that the language should be high-level. C is definitely not appropriate: it forces the programmer to take care of those messy details and may make the student focus more on the architecture (which is in fact only accidental) than on the computation itself. Understanding memory management and stuff is very important, but not on this level.
Java, on the other hand, may be a bit overwhelming. Just think about the amount of code you have to write and concepts you have to introduce in order to get the mere "Hello world"... Also, the vast amount of available libraries is paradoxically a disadvantage: code reuse is great, except (again) not at this point. Learning Java forces the student to learn how to use the IDE: writing Java in a plain editor is probably not the best idea.
Python or Ruby may seem not bad: they are both high level and extremely easy to start doing stuff. Their design is focused around being practical, though, and that means that for sake of efficiency and practicality they discourage some important programming techniques, like recursive functions.
This leaves us with high-level, “academic” language, like Haskell, Prolog or Scheme. The first two base heavily on some nontrivial concepts (like declarative programming), so my number one choice would be Scheme. Scheme is a very small language with very few special cases, making it easier for students to concentrate on the important stuff. Their errors will be more likely to be related to actually thinking something wrong rather than misunderstanding the subtleties of the object system. Finally, there's SICP, which makes a very pleasant reading.
Note that the slightly alien outlook of Scheme (with the funny syntax and so on) is an advantage in this case. For students with prior exposure to some programming (hacking PHP pages and so on) it will be easier to drop any bad habits they may have caught, and the rest... well, the rest doesn't really care, as anything would be totally new to them.
Of course, the next thing to learn should be some serious, industry ready language. C, C++, C#, Java, Common Lisp, Fortran---take your best shot. Let the students at least have nice memories of their junior programming course :-)