I think I would introduce Java, it's probably the easiest language to start with, and it's the one I know the most.
As for the format, I'm thinking that I can actually make a blog with the lessons and exercises, and have all the feedback, corrections and whatnot in a single thread under Social. What do you think?
Yeah, sounds good. I'm sure a lot of people here would be interested. Especially if you went into the game dev side of things eventually
Please, do one thing though. Don't make it dull. Crack a few jokes, put references and stuff in the code, doesn't matter. Be as subtle with it as you like, but if there's anything I've learnt is that it's damn near impossible to learn when you're bored.