Todo depende de lo que quieras aprender.
Si quieres empezar aprendiendo las bases, deberías comenzar con C o C++, el primero es un lenguaje estructurado y el segundo es una extensión de C con orientación a objetos.
Si quisieras seguir intentándolo con Java, te recomendaría el libro
Como Programar en Java, de Deitel que es súper ameno (el de Piensa en Java es demasiado complicado si lo que quieres es empezar). En este libro te enseñan a crear interfaces gráficas desde el principio, pero tiene una muy buena curva de aprendizaje.
Del mismo autor, existe
Como programar en C/C++, que es del mismo tipo del anterior, con muchos ejemplos y muy fácil de aprender también.
Luego existen también manuales como
Aprenda ... Como si estuviera en primero, que son libros web gratuitos de varios lenguajes (C,C++, Java, ...). El link es :
http://www.tecnun.es/recursos/labmat0.html
Yo te recomendaría primero empezar con C para asentar los conocimientos y luego avanzar a lenguajes de más alto nivel.