No es para nada necesario aprender a programar en C++ para luego pasarse a Java, vamos que no tiene ningún sentido. Para aprender programación orientada a objetos necesitarás ver ejemplos y hacer ejercicios, y eso lo puedes hacer en Java perfectamente, pero como te dije en el otro hilo, es bastante mejor que empieces con aplicaciones de consola, intentar aprender a programar al mismo tiempo que tienes que aprender todas las historias de Android (Actividades, Intentos, etc) no solo va a ser complicado, si no que te puede dar un visión equivocada ya que todas esas cosas no existen en cuanto salgas de Android.
Sobre lo de aprender a nivel medio-alto, realmente saber programar de verdad va más allá de saber usar un lenguaje, es cuestión de empezar a saber más de diseño de una aplicación completa y saber cuando crear una clase y cuando no, si tal método debería ser público o privado, si debería estar en esta clase o en la otra, quien hace qué y cómo, quien llama a quien, etc, y eso es algo que vas a tardar años en hacerlo de forma aceptable y te vas a tirar toda tu vida perfeccionándolo.
Si sabes inglés puedes empezar por aquí para ir enterándote un poco: http://docs.oracle.com/javase/tutorial/java/concepts/index.html