I started on C++, Only programming knowledge i had was from basic on the Amiga & Earlier commodore systems. I got a few C++ books which i found easier to learn from rather than reading them on a computer mainly because its quick to find reference to things.
I only started on C++ because i always heard people talking about how all the "pro" devs use it to make games etc, But now with about a years programming learning i think i should have started with Java, Much of what i learnt in C++ i could take to java, So it wasnt a total waste.
I also tried C# which i actually find a very good language & i like XNA for some simple game stuff, But i do find myself a little frustrated at being able to only deploy on windows machines Rather than anything with a JVM.
I think whatever you learn first there is no "wrong" or "right" once you learn some concepts & how to control the flow of a program you can take all that with you to another language.
Coming back to your main question i think everyone is different on how long it takes to learn, For me i feel very beginner still now & i been learning for about a year but not full time, I come and go at it when i feel like it.
I had C++ In easy steps & C++ A beginners guide to start with, Found both pretty good. Also if you after doing some C# I recommend Head first C#.
Good luck