I know this will date me somewhat, but growing up I really enjoyed P-Robots. There's a really simple goal (beat the other robots), a simple API, and a short amount of time between changes to code and seeing the results. It segues into AI, design patterns, and even larger-scale code structure (some of these robots can get pretty big -- and what about sharing code between robots?). If you can find something similar but newer it would be a good way to get the "getting started programming" part. Suggestions:
Once that's done, consider going for a really simple 2D scrolling shooter, platformer, or similar "arcade-style" game -- you can use SDL or XNA or whatever's most familiar. Even getting a pong clone up and running in these is not entirely trivial. This gives you a small echo of what it's like to build something "ground up".
After this, explore: a mod to an existing 3d game (a new object, or a bot, or something) to give a little insight into larger engines.
The keys, from what I've seen, seem to be:
- rapid iteration: the ability to see results quickly
- prototypes: many small experiments to get breadth of experience and confidence (okay, how would we do a marble game? how about space invaders? etc)
- exploration: learning to love looking into how other peoples' games are built, tweaking them, etc