Depends on what you want to achieve and your current skillset. I'm taking this from the point of 'I want to learn gamedev' rather than 'I want to learn language X and gamedev'. Since you're comfortable with C++, I advise using that. The other major advice here is start 2D. It's more complex than it looks, so starting as small as possible is good. (Nobody wants a 1D game.)
Then it comes down to what you want to do. The two routes are going to be using a lower-level graphics library, such as SDL or SFML, against a higher level graphics engine such as OGRE3D or its 2D cousin, TROLL2D. I would again advise the former. You gain a lot more from making your own little rendering routines (I'm not meaning rendering routines as shaders and the like, but more how sprites work) rather than using what people have done.
Start small. Tetris may seem small, even Mario might. But these are still pretty big. I advise something like Tic-Tac-Toe if you aren't sure - no real time involved. But you would still need graphics, some AI, winning, a game loop, etc.
If you want to aim a little higher, Pong is good. It is real time, so you would need real-time input, as well as collision detection (bounding boxes), better AI, maybe a simple menu. All this will teach you important skills.
Then try Tetris: you've got timers, random generation, more collision detection. Then PacMan or something. After you've made a few, you can go more wild.
All it comes down to is practice. It's quite possible to learn gamedev by coding a 3D RPG in C++ (let's say you can, for example's sake) when the closest you've done to any programming is Excel macros. You would get there, but it would take an awfully long time from all the stuff you have to learn. Not to mention the fact you'll probably give up from finding it too difficult.
