A lot depends on how you are planning to "learn" how to program.
Academically? Do-it-yourself?
Are you completely new to programming?
Learning how to program, and learning to use different program languages are quite different issues. However, the catch is you have to learn how to program using one language or another. You *could* start with one of the "easier" languages, like you mentioned, but then you will not learn some of the key concepts present in other languages (like pointers in C++, if you choose to go with Java).
In the academic route that I took, the first language taught was C++ as part of an introduction to object-oriented (oo) programming and I thought this was a good choice and a good language to build a foundation on.
Mind you, I had previously (in high school) spent some time using different forms of "BASIC" and Turing languages, so I wasn't a clean slate altogether.
It's hard to say how a certain individual will take to something like C++, it very much depends on the type of thinker you are. Having been a teaching-assistant in a first-year University course on programming (with C++), I can say first-hand that some people take to it easily, and enjoy it greatly, while others struggle with ideas presented to them, no matter how much thought they put into it. And both groups of people may very well be intelligent, but one is perhaps more of an analytical thinker than the other.
How much programming you need to know for trading jobs, I have no valuable insight on.