I'd recommend basic C, it will give you a great grounding for pretty much any language that you want to move onto in terms of desktop/client applications. Move onto C++ and object-oriented programming once you're comfortable with the procedural nature of C applications.
Linux is a great start - I started developing with VB on Windows with Visual Studio at school, and subsequently had to unlearn all of my bad habits when I started more serious coding. I'd go for an Ubuntu installation for the fuss-free install, get a compiler setup and open up a text editor to start pasting some code examples.
To install the gcc compiler in Ubuntu, go to the console $ prompt, then type:
Code:
$ sudo apt-get update
$ sudo apt-get upgrade
$ sudo apt-get install build-essential
You can then compile any C code by going to the directory that it's in, and typing:
Code:
$ gcc <source file>.c -o <executable>
To run the executable, type:
This site is a great resource: Cprogramming.com: How to Get Started with C++
It should point you in the right direction, there's loads of well written tutorials on there to work through: Cprogramming.com Tutorial: Introduction to C
Also worth mentioning; don't try to run before you can walk, the "complicated" concepts like low-level procedures and playing with pointers will seem far easier if you've got a grip of the basics. Skipping ahead to complicated concepts before you've got a grip of the basic concepts will just lead to frustration (speaking from experience).
Hope that helps, have fun!
Bookmarks
Algorithms and Data Structures
Java tutorials
Algorithms Forum