1. "We're going to ask you to build real software, with real tools, in a group. Even if it's only for one course."
2. "We're going to ask you to do some theory and write some proofs."
3. "We're going to show you some wild stuff that looks like it belongs on an alternate timeline."
(3) might be something like Oberon, or Racket, or some eccentric faculty project. Or even just teaching all your CS majors Haskell, if you don't have any genuinely eccentric faculty projects to inflict on students.
Innovation is often driven by people who are aware of what might have been.
For those that want CS theory only, there is applied mathematics into computation majors.
Do you start more abstract, and if so with functional, imperative or OO underpinnings? Do you intend to switch languages rather soon or later?
The good thing about Oberon, language set aside, is that you could get started without a lot of adminstrative debris. No 80% of the screen covered in an IDE, not even a big ol' "public static void main" that you're told to gloss over.
I can see good arguments for sticking to one language throughout many courses, too. Sadly that often means C++.
We got taught Eiffel Freshman year, C and Haskell Sophomore year, and after that, whenever a course used another language (Java, C#, C++), the prof just said "you'll pick it up".
(That's leaving out the usual-for-academia-but-still-weird stuff like MATLAB and Verilog)