Python is a good place to start. It has a very consistent syntax and lets you concentrate on the high level issues of your programming problems. It is designed for readability. Perl is designed for expressiveness, which makes sense given that its creator is a linguist. C is good for learning the particulars of how a computer works. It is often described as a high-level assembly language. Shell scripting will help you learn the tools approach that Unix systems are built on. Learning the shell is actually a very good introduction to programming, because much of what you do in a shell is useful in other programming languages. The shell IS a programming language. It's strange, as programming languages go, but it has a lot to teach you about programming and Unix. It is no laggard either. Serious applications can be coded in shell. I once wrote a custom content management system for three web sites entirely in shell.
I suggest you visit the IRC channels #bash, #python, #perl and ##c on freenode. Pay particular attention to the links provided in each channel's welcome message. You will get pointers to tutorials and other useful resources. You should have no problem locating tutorials more pertinent to Linux from each channel.