I taught 2 100 level programming classes as an adjunct professor once and used C#.
I'm a Python web developer now and think it would be the ideal language to use for teaching. It has all of the important OO concepts baked in, and the interactive aspect makes it a very very easy language for beginners to learn.
Frankly though, C, Java, C#, or Python all seem like fine options. Each is probably best suited for certain audiences, but any of them are better than C++ and PHP.
While C++ and PHP are very popular languages, no one should learn them first. They're both hideous to look at (which matters to beginners), and in the case of PHP, just very hackish and lacking in good structure.
Start with pygame. Everybody loves a good simple game.
Just my $0.02 though.