We all realized early on that object orientation would muddy the mix somewhat. This was evident in seeing that many data structures texts using c++ were not really using any OO. But even though we wanted to develop polymorphism in a strong way and approach data structures from as much OO as possible, it seemed apparent to me that in this (for us) third course we really MUST expose students to other important ideas/paradigms, eg. generics. Naturally, that brings up even more the idea that we seem to be cramming too much into the beginning curriculum. Dan McCracken picked up on that in putting together his panel at SIGCSE last year.
At this moment, things are not very clear in my own mind concerning how things should be done in CS2 (or even in our second and third courses). Certain things make very strange bedfellows: OO design methodologies, classical software engineering, polymorphism, generics, data structures, object structures. I'm hoping that by participating in this workshop some of my thinking will crystallize into a reasonable structure for our curriculum.