I'm also very interested in programming games. So far I haven't found any that are exactly what I want, but there are some enjoyable ones.
I used to do programming contests in college, while I enjoyed these I always felt like I wasn't learning enough. They're designed so that you'd need a very good team and lots of outside training. It isn't nearly as much fun outside of real (or even practice) competition, but you can find big banks of problems and an online judge if you want to play along. TopCoder is similar and much easier to participate in, but again its focus is on competition, not education (though maybe that's changed?).
The closest I've seen in video games are those by Zachtronics Industries, they all deal in some way with engineering design. SpaceChem in particular is quite programming-like (as explored here) and has a great difficulty progression. Kohctpyktop is an integrated circuit design puzzle with a strong test driven development bent, though if I hadn't already studied EE it would probably be prohibitively difficult.
There's also pleasingfungus' Manufactoria, which has a lot of CS (stack machine) stuff in it and a great sense of progression.
A lot of these attempts tend to be directed at kids; the old Rocky's Boots was one of the first steps in this direction, with logic gates and simple circuits. I didn't find it very good, but ToonTalk is an ambitious visual programming environment and game-like tutorial rooted in SmallTalk semantics.
Cort Stratton wrote a post in September called The Games Programmers Play, which covers this topic well. The comments here on Slashdot and on Gamasutra suggest some more such games.
I've been doing a lot of thinking about designing "games for learning programming", I've written somewhat more extensively about it on my blog. I hope you find some of these suggestions interesting, sorry for the linkstorm.