I guessed C++ would be the best because all the games I've seen so far (both indie and company ones) are made in C++.
C++ is the industry standard for AAA, cross platform titles with hundreds of devs or skilled indies. C# is much easier to start with.
Minecraft in special is made by one guy, and yet it's still better than a XNA game, made by one guy too: Terraria.
Minecraft is made in Java. So that doesnt quite waork 100% with your argument, but I get the gist.
I don't wanna be stuck with terraria-like games if I learn XNA
While I havent played Terraria, XNA is one of the most widely used engines available and game quality is almost always a result from the programmer and people working on the game, not the engines. There is some quality stuff from Indies on the Xbox Live Arcade, and that is all made in XNA. No matter if you make your own engine, you are still limited by either OpenGL or DirectX - unless you write your own drives, which you cant - and most engines implement almost everything available from those libraries.
I would first recommend you learn C++ or C#, and use a simple-ish game engine like SFML or XNA, just to get a tast for programming, and then use either of those until you hit a limit with an unsupported feature etc, and then move on to your own engine if you need it. Just get some code examples for GL or DirectX just to see what youre getting into with your own engine.
Regarding tutorials, as programming is text based, most tutorials are in text form. just search for c# tutorials etc