edit : me he dado cuenta que he venido a decirle a #1 algo similar a lo de #2
En orden de paradigmas diría que es más intuitivo aprender primero programación estructurada y de ahí poder derivar a OOP y similares, aunque tampoco pondría muy en primera prioridad esto. Lo digo más que nada porque estructurada tiene la propiedad parecerse mucho a lo que la gente que no conoce el mundillo se imagina que es la programación. OOP me parece demasiado "abstracto" para un novato.
La idea es que aprendas la base de la algoritmia y metodología esencial y que veas el lenguaje como un mero soporte. Deformar una solución inicial y sus ideas a las propiedades y limitaciones de un lenguaje es algo demasiado común, si empiezas ya sabiendo evitar esto ganas bastante.
Mi recomendación personal es que si te manejas con el inglés (y si no te manejas y te quieres dedicar a esto, aprende) le eches un vistazo a alguno de estos cursos (los tres primeros eh!) :
http://see.stanford.edu/see/courses.aspx
Sobre software a utilizar si empiezas con C, te recomiendo el CodeBlocks+minGW mismo (disponible tanto para win como para linux) :
http://www.codeblocks.org/
Si usas Mac, el Xcode+gcc son una maravilla también (de hecho Xcode es de las cosas que más envidio de Mac).
Python no te lo recomiendo por varios motivos. El más general que te puedo decir es que es un mundo aparte,y empezar utilizando eso te va a generar unas costumbres poco aceptables cuando trabajes en otros lenguajes.
Como último consejo, decirte que con que te aprendas la estuctura básica de cualquier lenguaje vas sobrado. No necesitas aprenderte de memoria tooodas las utilidades de las librerías estándar. De hecho es bastante común para casi cualquiera ir haciendo pequeñas consultas sobre algun método concreto y tal. No pierdas el tiempo aprendiendo cosas inútiles.
