I'll throw in my own two cents although I believe this subject is a bottomless pit. Don't get me wrong, I think it's a fascinating question, but probably not one we will solve here to everybody's satisfaction.
In a nutshell, I'd say that the language should do what you want it to do, in a simple and unambiguous a way as possible, and not more.
My own experience comes from tutoring several generations of first and second year students with the Oberon programming language. People who know this language will recognize its influence in my opinions. Note that this language was used to teach "Algorithms and Data Structures". At the time (back then), functional programming and object-oriented design were taught in separate courses as of second year.
Important: Before going into the specifics of any language, however, I would like to emphasize that the most important thing is to be absolutely clear, to yourself and to your students, about what the goals of your course are. Are you teaching programming per se? Or algorithms and data structures? Or software engineering? Before choosing a language, it's worth it to think a moment about where you're going with it. Differences at this level (goals) is what probably, in my opinion, leads to most disagreements on this topic.
The points I consider important may overlap with several things that have already been said, but I believe most end up being subsets of one of the following four:
Simplicity: The students are usually there to be taught programming, algorithms and data structures, and not the features and intricacies of any specific programming language. Wirth used the Einstein quote "Make it as simple as possible, but not simpler" as a guiding principle in the design of Oberon, and there are several other languages out there that do it just as well. Your programming language of choice should be able to implement all the concepts required in your lecture, but should do this with the smallest possible set of features/details. The programming language is usually just the tool, not the goal.
Unambiguity: A close sibling of simplicity, there should be one construct for each concept, with as little overlap as possible. Think of it as there being only one "right" way of implementing every concept. Three different types of loops that semantically all do the same thing? Or fifteen different ways to increment a variable? Not good. This also makes correcting homework or generally just understanding your students' code a lot easier. Your teaching assistants will appreciate it.
Portability: Students will go to class with Linux, Windows and OSX machines, and the programming environment should be as similar (identical) as possible under all three. The results of any program should also be identical. This is another point that the teaching assistants, responsible for marking homework and dealing with questions/problems, will greatly appreciate.
Industry preference: Seriously, we should start worrying about this only if "Industry" itself ever decides what programming language it likes best. Since the invention of computers this has been a constantly-moving target. For the moment, if your students really learn how to program, then it won't be language-dependent. There are, however, some areas where industry manages to agree on a standard, e.g.
VHDL for circuit designor SQL for database queries, so this is still a valid point.
Again, how a language fits this list is strongly dependent on what it is you're trying to teach!