I think the best way to learn programming is to work with something where you have instant gratification for your efforts. In the modern world, this is usually best served with apps or websites.
For programming, the important hurdle is rarely grasping the syntax or idioms of a particular language, but rather understanding how the various components can slot together, and the process one must go through in order to solve a problem. In this respect, the actual language might not matter so much.
Java's a good shot (it's quite suited to building Twitter clients, to-do lists etc as well, so don't worry in that regard). It doesn't really have any horrid issues, and certainly not at the level you'll be looking at it.
I have another two solutions though:
Python. It's a brilliant language to learn programming with for the first time, being both rather rigorous in its approach and relatively easy to grok and write. Picking up a framework such as Django early on to write web applications with is a good way to use it to approach some personal projects (and this would later involve having to learn bits of HTML/CSS).
C#. It's a great language and MSFT have some good guides. In particular, why not write some Windows Phone apps? The emulator is pretty awesome so you don't need an actual phone, and writing the app itself is free (distribution on all the app stores costs a small fee). It's a... fun environment to play in.
