Puedes empezar con el lenguaje que quieras, C y C++ son muy buenos lenguajes, pero casi no se enseñan como lenguajes para principiantes (aunque que eso no te desanime si estos lenguajes son los que quieres aprender). Yo empezé a programar con Visual Basic, de hecho con el tutorial que está en este sitio web. Python ahorita está muy de moda para aprender a programar, te puedo recomendar este PDF gratuito que es muy bueno. Java también es enseñado bastante como lenguaje para principiantes, ahí sí te recomendaría libros en físico, como el de Deitel "Java como programar". Ahora, si lo que te gusta es aprender interactivamente, Codecademy ofrece excelentes cursos interactivos para Javascritp, Python, PHP y Ruby.

¡Saludos!