Hola Mariano,
en un principio quiero comentarte que no, que no conozco ningún tutorial de java que proponga ejercicios, está éste que es muy completo y empieza de cero, que, si como dices, has estado buscando ya lo habrás visto:
http://www.cica.es/formacion/JavaTut/
Yo también hace días que empecé con Java, al principio parece chungo pero creo que no lo es tanto, es programación orientada a objetos pura y dura, intenta aprender bien las bases de este tipo de lenguajes y luego pasa a aprender la nomenclatura y la sintaxis de java. Luego, poco a poco, irás aprendiendo a usar las clases que ya te vienen dadas, pero en un principio dependerás mucho de saber usar documentación.
Respecto a los terminos que nombras has de pensar a grandes rasgos:
Virtual Machine: lo que necesita java para hacer correr programas, ya que los compilados de java no los lee windows (p.ej.) necesitas pasarlos por este "filtro" para ejecutarlos.
SDK: Clases necesarias para empezar a programar en java.
Documentación: Explicación detallada de las clases de java con sus métodos y propiedades.
IDE: Entorno gráfico para programar en java, no es necesario, pero sí te hace la programación más cómoda:
Empieza pillando eso: Virtual Machine, SDK y documentación de una misma versión. Y sobretodo:
MUCHA PACIENCIA
Espero haberte ayudado algo
