I'd start here http://www.squeakland.org/ the environment is based on smalltalk 80 and is pretty pure OO, so even though it looks like a toy they will 'get their mind right'.

On the surface it has a fantastic drag'n'drop tile based scripting layer that allows kids to quickly get toy and demo things working - building both familiarity with concepts, confidence, and interest. This http://www.squeakland.org/school/drive_a_car/html/Drivecar12.html jumps into instructions for a 5 minute draw a car and write the program to bind it to a drawn steering wheel. You can quickly progress to programs with sensors doing track following. I've used it to make flocking games (like herding cows etc) for the amusement of my kids.

It is intended that you can drop under the scripting and start using the full OO smalltalk (http://www.squeak.com) classes, inheritence, coding while you debug while you run. OS integration, OpenGL bindings, links to DBs, multimedia, a whole host of good stuff.

The idea is to give them something it's easy o come to grips with but that is OO, open, and as deep as you want to go.