Es una pregunta bastante sencilla y habitual, pero cada maestrillo tiene su librillo. Hay varios grupos de librillos:
Los que recomiendan C/C++
Suelen ser la misma escuela que te recomienda seguir después con ensamblador. Lo que vas a aprender de esta forma son conceptos como los punteros (muy importantes) y vas a conocer el ordenador a un nivel bajo (es decir, muy cerca del hardware). La abstracción que proporcionan estos lenguajes es poca.
C y C++ son lenguajes que se utilizan precisamente por su bajo nivel y por generar código eficiente, por lo que se siguen utilizando y se van a seguir utilizando por mucho tiempo. Si lo que te interesa es programar al más bajo nivel: microcontroladores, sistemas operativos y librerías del sistema operativo, sin un lenguaje que te restrinja y evite los segmentation fault (tal vez los busques) entonces C y C++ son para ti.
Si te interesa la eficiencia pero no quieres preocuparte de los problemas de memoria tal vez otras opciones como Julia o Rust sean mejores.
Los que recomiendan Python
Python es un lenguaje con una sintaxis sencilla y parecida a pseudocódigo, heredero de la tradición de Algol, que intenta acercar el lenguaje de programación a la forma en que se describe un algoritmo.
La gente de esta escuela está por tanto más preocupada por la algorítmica, comprender la complejidad de los programas (la notación de la O) y no tanto por punteros y eficiencia de memoria.
En el caso de Python, la disponibilidad de librerías que permiten hacer muchas cosas de forma relativamente sencilla lo hace muy atractivo, prácticamente es el lenguaje por defecto para los que programan pero programar no es su tarea principal: lingüística computacional (nltk), estadística (pandas), y un largo etcétera, incluso reemplazando a otros lenguajes que tradicionalmente tenían este nicho (R, Matlab, Octave, etc.)
Otros lenguajes en esta categoría son javascript (con una sintaxis no tan elegante) y CoffeeScript, que acerca lo que es javascript al mundo de Python. Son opciones interesantes porque permiten programar para web, lo que significa que podemos hacer pequeñas extensiones para el navegador (como GreaseMonkey), Apps para dispositivos móviles, páginas web y servicios web (también del lado del servidor, ya hay cierta tradición full stack como MEAN). Poder aplicar lo que se aprende es muy satisfactorio, especialmente para los novatos.
En algunos casos se puede recomendar Lua, porque es un lenguaje muy sencillo y con una sintaxis simple y breve. También Ruby por motivos similares.
Los que recomiendan Java
Java ha sido por mucho tiempo el lenguaje más popular, puede que aún lo sea a día de hoy. Es un lenguaje muy utilizado en las grandes empresas de software porque simplifica la programación en C con un recolector de basura y una máquina virtual que abstrae los detalles del hardware sin perder demasiada eficiencia (aproximadamente el doble de tiempo que C). Por la ayuda que proporcionan los IDEs es un lenguaje bastante popular hoy en día para enseñar programación.
Hay mucha demanda de programadores en Java, y también mucha oferta. Si sólo quieres aprender un lenguaje (y nunca más ningún otro) probablemente (a día de hoy) Java sea la mejor opción. Por lo competitivo del mercado prepárate para aprender también un montón de librerías y tecnologías, como Hibernate, Spring, Maven, SOAP y muchas otras. Tal vez no tengas muchos lenguajes para poner en el CV, pero eso no significa que sea breve, realmente el valor de Java está en todo el ecosistema que tiene alrededor.
Java es un lenguaje con un uso muy extendido, pero también muy odiado, lo que ha propiciado la aparición de otros lenguajes como Scala y Groovy entre otros.
Los que recomiendan Pascal/Delphi
O los que recomiendan Ada. Se basan en conocer los ordenadores y la programación de una forma algorítmica, como Python, pero no a tan alto nivel, conociendo algunos detalles de implementación, como C, y sin olvidar los tipos y la teoría de tipos (también presentes en Java, aunque sólo en POO), también algo importante si quieres poder participar en los clásicos debates de tipado estático frente a dinámico.
Son de la escuela: "La letra con sangre entra", o alternativamente: "no quiero que me preguntes si el compilador te dice que tienes un error". Eran la opción para aprender programación estructurada por lo que ayudaba el compilador a detectar errores, eso reducía la carga de trabajo de los profesores. Han sido relevados por Java (que es POO) porque realmente lo que se valoraba de estos lenguajes es eso, si hay que enseñar POO, se enseña, Eclipse y Netbeans ya te informan de los errores antes de compilar.
Resumen: Si alguien te recomienda Pascal, Delphi o Ada, está desactualizado y lo hace por los motivos incorrectos.
Los que recomiendan Lisp
O Scheme, Clojure, ClojureScript, Haskell o Prolog. Valoran conocer la programación funcional o declarativa, el aspecto más teórico de la programación (más que la algorítmica), como es el lambda cálculo, la lógica, la unificación, los árboles sintácticos, las macros y la homoiconicidad.
Son lenguajes que te dan una perspectiva interesante de las cosas. Pueden no ser los lenguajes más prácticos para hacer algo concreto, pero conocerlos te puede ayudar a abordar un problema aunque lo resuelvas con otro lenguaje. Son más un lenguaje a aprender que el primer lenguaje a aprender, pero ciertamente son lenguajes a muy recomendables. En el caso de Prolog es prácticamente el único en su paradigma (¿hay más?).
Es curioso porque los lenguajes de este grupo los verás poco por el foro. Son más lenguajes para la gente que quiere hacer las cosas bien que la gente que quiere hacer algo y que funcionen. La gente que pregunta cuando ya ha resuelto un problema si lo ha hecho bien y cómo podría mejorarlo (revisión de código), en lugar de la gente que pregunta porque no ha mirado la documentación y no es capaz de encontrar el fallo en el programa que ha escrito o porque ni siquiera sabe por dónde empezar a escribirlo.
Los que recomiendan PHP
PHP es un lenguaje muy popular por la tradicional LAMP. Todavía hay muchas páginas que funcionan con PHP por detrás (como este foro) y eso le garantiza sobrevivir por mucho tiempo. Fue un lenguaje que cumplió con una tarea decentemente y fue prácticamente la única opción para quien quería hacer algo en ese nicho, lo que garantiza que mucha gente lo use. Por el diseño del lenguaje también se garantizó que mucha gente lo odiara.
Quienes te recomiendan empezar por PHP son mala gente, no les escuches. Tampoco escuches a los que te recomiendan VisualBasic, Perl, Brainfuck ni Malbolge, bloquéales en cualquier red social en la que puedan llegar a ti. Es broma, simplemente es una opción extraña y no está muy claro si te va a enseñar a programar bien o a programar mal, mejor cualquier otra.
Los que recomiendan Bash
Son administradores de sistemas. Bash es muy potente, pero nadie lo toma en serio como lenguaje de programación y nadie te tomará en serio como programador, aunque consigues un +10 en frikismo y es muy satisfactorio poder arreglar algo simplemente con un script. Además, para cualquier cosa que haga el SO (como mover ficheros) es más eficiente que hacerlo tú mismo en C (ya lo hace el SO) y también tienes muchas herramientas (en lugar de librerías) para usar, como grep, sed, awk, etc.
Si te interesa la administración de sistemas, es el lenguaje a aprender, o tal vez csh, o PowerShell, seguramente todos. Pero es raro que alguien recomiende empezar por uno de ellos, hazlo por tu cuenta y riesgo.
Los que recomiendan la familia .NET
Tradicionalmente se ha asociado con Microsoft, especialmente para el desarrollo de aplicaciones de escritorio, aunque ahí está ASP.NET para solucionar eso. Para Linux está la alternativa de Mono, pero aun así parece un intento fallido por parte de Microsoft para capturar el mundo de la programación.
La estrella indiscutible, C#, se usa en muchos entornos industriales, pero siempre por detrás de C y Java, es difícil encontrar excusas para apostar por C# en lugar de uno de los otros dos, que por otro lado tampoco son los líderes indiscutibles de la lista (aunque sí pueden ser líderes discutibles).
Los que recomiendan LaTeX
No quieren programar, quieren \emph{publicar}. Hay lenguajes de programación que son Turing completos pero tienen un uso específico para el que están hechos, otro ejemplo es XSLT. Si lo que quieres hacer es eso, puede ser la mejor opción, pero sólo para hacer la cosa concreta para la que han sido diseñados. Lo mismo con ActionScript y Flash.
Los que recomiendan Go o Erlang
Gente muy centrada en la concurrencia. Seamos honestos, si tuvieras un cluster o un grid bajo tu responsabilidad no estarías leyendo esto, así que me ahorro escribir esta sección.
Los que recomiendan otros lenguajes
Son gente muy rara, pregúntales por sus ideas políticas.
Puede que os interese poner esto con una chincheta o enlazado desde el FAQ o algo.
Si tenéis comentarios para mejorarlo no me importa incorporarlos.