One title per answer.
Core War (http://en.wikipedia.org/wiki/Core_war) is the classic, where two programs run in a simulated machine, each trying to halt the other one.
Discover fundamentals of computer programming by playing a board game; c-jump helps children to learn basics of programming languages, such as C, C++ and Java.
GNU Robots (http://en.wikipedia.org/wiki/GNU_Robots) is a great way to get stuck into Lisp.
Starship Soccer (http://www.geocities.com/siliconvalley/horizon/8596/StarshipSoccer.html) pits C++ controlled teams against each other, playing a mix of Space War and football.
Good list on Wikipedia!
Programming games of note include Core War, Robocode, RoboWar, Robot Battle, Crobots and AI Wars. Final Fantasy XII also includes some elements of a programming game, as the player creates the AI of his characters, although the player can also choose to directly control the action.
A little Flash game I found the other day: http://www.gameroo.nl/games/light-bot
Be careful, you will likely lose about an hour of your life ;)
Microsoft's Terrarium, which involved programming the intelligence of a creature using any .Net language, has now been open sourced to CodePlex
Robocode is a great way to learn Java and have fun doing it. You write Java code to program a robot, which then battles it out against one or more other robots. It's years ago I tried it, but I remember having great fun doing it. We even programmed robots at work (in between the real work ;) ) and had a small competition going to see who could come up with the best algorithms. Recommended!
Lists and Lists: An interactive tutorial by Andrew Plotkin.
"An introductory course in the Scheme programming language (a dialect of Lisp) presented as a text adventure - or, to put it another way, a Scheme interpreter with a wee scrap of text adventure wrapped around it. Since it's Z-code, and the first Z-code games were written in another Lisp variant, there's an odd circularity to it all."
- Carl Muckenhoupt