1) What language? [...]
2) What paradigm? Once you have decided on a programming language are you going to teach via an IDE? Text editor? How about[...]
For 1). I'd say it's very unrelevant, the point is to give outlook and possibility ot others as well. When I started learning coding at school when I was 11 (almost nobody had computers at home back then, my first was a c64, 2 years later), and we started with basic. Then, in high school they cycled us through 4 languages until we finished 4 years later (have to say, it was a math+CS class, and we had 4+4 hours theory and lab each week), but by our second year some of us geeks were already well ahead in coding knowledge -- and I think that was because our teachers were very good at the very beginning to make us interested.
My point is, I don't think the choice of language is such a big problem. The problem is when all they teach you is that language, and that needs to be avoided. Languages are just tools to bring your theoretical knowledge to life, they (it) shouldn't constrain you, but liberate instead.
As to 2). also, it's fairly unrelevant. Lots of us here didn't start with a fancy IDE or even a text editor :) If all you can say in favor of a language is that it has a fancy IDE, then you'd better drop it upfront anyway. Also, we already have anough newgen coders who can't work without an IDE. And that's not in their favor.