Eu apesar de gostar muito de Java e ser minha linguagem preferida, eu acho melhor começar por Python.
O Java já te empurra para a orientação a objetos, e vai ficar uma meleca tentar programar estruturado em Java, em geral dá ruim, aí o iniciante sai xingando a linguagem.
Sim!! Esse é um ponto que fazem muitas pessoas odiarem Java. Geralmente são pessoas que começam a faculdade sem ter contato com a programação antes e pega um Java logo de cara ai assusta mesmo.
Por isso é importante fazer uma boa base. Eu recomendo pra qualquer pessoa que começa a estudar fazer o curso CS50 de Harvard antes de escolher qual linguagem quer se especializar.
Mas eu também acredito que é mais fácil alguém que sabe Java aprender Python do que ao contrario. Lógico que não é impossível, mas é um pouco mais dificil
Também dá para começar com PHP, usá-lo bem estruturado, depois usar o PHP de forma orientado a objetos, acredito ser a linguagem ideal para se fazer uma transição, mas devido ao mercado , promoção extrema, etc. eu particularmente iria de Python.
PHP tem essa fama mesmo, de dar muita oportunidade a iniciantes. Mas particularmente, o PHP cai de uso a cada ano e por mais que esteja em 80% da web como dizem, a maior parte disso é por conta de plataformas como o WordPress.
Obviamente que tem muito sistema para dar manutenção em PHP e acredito que é dai que vem tantas oportunidades.