I absolutely beg to differ on your first point. You don't use actual performance measurements in Data Structures courses, no matter what language you use. You aren't instrumenting your code or counting bytes or anything. You measure the concepts by analyzing with Big-O notation. If you really wanted to, you could teach a Data Structures course using just paper, pencil, and pseudo-code.
Pretty much any language will work fine for teaching data structures.
Pretty much any language will work for teaching data structures badly.
If your instructor is showing you a cool animation of a list with less than 30 elements being sorted by X algorithm, he's doing it badly. Or at least if that's all he's doing. There are by the way many schools that do just that, under the rationalization that the point of the class is to have the student practice what he learned at Programming 101. I attended such course in the day, and then went to teach the same course some years later, but I don't think the results were any good.
IF he have you run your algorithm against input taken from /dev/random, first 100KB, then 1MB, then 10MB, then 100MB he's a little less bad. IF he makes you do the whole sequence a dozen times an plot each resulting data points in a graphic with logarithmic scale, he is not bad at all.
Then you can start to discuss Big-O notation, but for the resulting graph to make any sense you need that the program written by the student to have a relatively strong correlation with what the computer is actually doing. It will not do, by example, if the runtime environment decides to implement you list as a dictionary object instead of a raw array. Also, having a relatively precise clock like Java's currentTimeMillis will reduce the possibility that you embarrass yourself if the practice do not seem to match the theory.
If the course is being taught at graduate level, you may want to run a second experiment, this time with input sizes of 1KB, 256B, 64B, 16B. At this point you will be able to discuss stuff like the Little-O notation, the constants involved in both notations, and how those are derived from Limits of the time function.
For this you will absolutely need the best clock available in your hardware, so C because a must. It will also help if you can run cc -s on your code and see what assembly is behind your code. I know it is overly ambitions, but that's how I would like to have learn about this stuff.
Pretty much any language will work fine for teaching data structures.