C would be my first preference as well, but I also appreciate that Scheme (or another functional language) would provide better opportunities than C or Java for students to learn more "advanced" algorithmic techniques such as recursion.

The problem with Java (and C, to a lesser extent) in basic problem solving is that you can almost brute-force-code and get a working solution that will get full credit, but after writing it a more elegant (and efficient) solution isn't always obvious. In functional languages, that "more correct" solution almost always seems to stand out more, at least to me.