The first game I made in C++ was Snake. Which was pretty simple and really just a test to see if I could properly use C++ and SFML.
Then I made Tetris, which wasn't too difficult but it took me a while to get the program design right.
Next it was Asteroids. Which was really cool, I used vectors and matrices, it's probably the first real use I've had out of my high school maths course.
And currently, I'm making Breakout. Which has turned out to be a much bigger project than the previous games. I've almost finished it. But I'm about to start adding functionality to my level editor which could take a while.
In my opinion, if you're just starting out, you should stick to classic ideas because that way when you're testing you have references that can tell you exactly what the game should be doing. You can still be creative and make changes, but for programming the core game knowing exactly what you're trying to build (i.e having requirements) will make things go a lot smoother. And it's a lot easier to get feedback about your game when people know the general concept of the game.
If you do that, then quickly you'll get better and be able to start making more and more complicated games which can incorporate strange and cool ideas that you've had. I'm quite excited to start learning 3D programming for example.
To answer your question, games I'm considering making next are Pacman (Because I haven't ever implemented AI), Mario (Because making levels would be an interesting challenge), Bust-a-Move (Because I would want to play that game!) and a pool game (Because of the cool physics it would use). I was going to make Space Invaders but I already made a rough prototype in Python and I think I wouldn't be pushing myself enough if I spent time on Space Invaders since it wasn't too difficult, the only challenging part would be making a level editor, which would be very similar to my breakout editor.
For reference, if you're interested. The source code and .exe files for my first 3 projects are online here https://sourceforge.net/projects/dujekcgames/files/
they only work on Windows7 32. They're poorly done though. It feels like every time I learn something new everything I've done up to that point becomes terrible. For instance, I didn't understand how to use header files properly until I started making breakout so my first 3 C++ projects have few classes and header files with no accompanying .cpp files and functions coded inside the .h file.
I've been doing the same thing. But I wasn't worried about making "cliche" games.