Take something like a data structure course. Data structures are completely independent of language. A rather lot of CS offerings do their data structure course in Java. Why? Java is the last language I'd use for teaching data structures, because you'll be forced to view all your data through the eyes of an object. OO is not useful for learning data structures, and will likely get in the way. Not only is Java a not good language for this task, it's an outright bad one, since the point is to learn data structures, not Java's obtuse way of implementing data structures. C would be a much better (though still not perfect) language choice, and LISP is probably better still. Leave Java for a Java class, if you must.
If I'm going to take a Computer Science major, I actually want some Science (or rather, research). If it's going to be about making applications, then it should be called "Software Engineering" or somesuch. Something to make it clear that the goal is practical applications, not research and theory.
"There is no shame in being self-taught, only in not trying to learn in the first place." -- Atrus, Myst: The Book of D'ni.