Hola.
Una recomendación personal, si recién empezas y no entendes mucho te convendría instalar Linux en una Maquina virtual como el VirtualBox por ejemplo (si tenes una maquina mas nueva que esa,
), te lo recomiendo porque al principio uno no entiende mucho y por lo general hace macanas y es bueno tener acceso a internet para saber como corregirlas cosas.
En cuanto a la distribución Ubuntu o Xubuntu te va a ir mejor porque son las que mas se usan y vas a encontrar mas foros e información en internet.
En cuanto a lo de programar, tenes que saber java, no es complicado, soy de la UBA y ahí no nos enseñan Java, Pascal, o C, nos enseñan los paradigmas y los lenguajes los aprendemos solos, es cuestión de aprenderse un poco la sintaxis (los nombres de los comandos) y salís adelante, el tema es que si sabes solamente Pascal se te va a complicar, Pascal es un paradigma estructurado y Java esta orientado a objetos, son mundos un tanto diferentes, te digo porque al principio me costo cambiar la forma de pensar para programar bien en objetos.
Agrego un comentario, podes programar tranquilamente en windows para android, es cierto que android es linux pero no estas accediendo directamente al sistema operativo, trabajas sobre la maquina virtual de java, pero mas precisamente sobre la maquina virtual que tiene android, así que no tenes ninguna ventaja al estar en linux en tu PC, todo lo que hagas no lo vas a poder correr en una PC común, vas a necesitar un emulador de celular (viene con el SDK de android).
Si queres empezar a hacer algo en android y no nunca tocaste linux te recomiendo que te inicies en windows porque se te va a complicar configurar las cosas en linux y por ahí te frustras, seguí los tutoriales de la pagina de android
Saludos