I'd suggest starting with Visual Basic or even C#/Java. Once you get at least understand the basics of those learning C++ will be way easier.
I'd disagree with your advice to start with Java.
Java isn't that newbie friendly, because you have to understand object orientation to do almost *anything* effectively. Sure, you can learn to knock together some simple programs without really understanding things like classes and namespaces, but it's hard to progress any further without grasping OO.
My recommendation? I still think C++ is an excellent starting point. With C++, you:
* learn a lot about memory management and the ins and outs of data structures (even when you switch to managed languages, this knowledge still helps)
* can start with purely procedural programs with basic functional structuring, then gradually move on to object orientation
* you learn a lot of concepts you'll use in Java anyway
* you're given a lot of room to fail, which forces you to write with discipline
Alternatively? Why not Python? I've enjoyed using Python for my own projects - it's extremely readable, it supports true object orientation and it isn't intimidating to newbies at all. I'd be tempted to say that Python is the new BASIC. No, I'll go further: Python is the language that BASIC tried (and failed) to be: a truly accessible, truly educational and truly useful programming language for the ordinary enthusiast.