To download Linux you must have a broadband connection, cause you are downloading huge files. Take a look at: www.linuxiso.org.
This is a great resource to learn how to download and burn a linux install cd.
If you plan to buy a box:
Even Amazon.com can be helpful.
In Europe, SuSE is the most used commercial Linux distro. I'm guessing it must be easier to get technical support and stuff.
There are linux programs that allow you to use the msn network. Not the same as you already know, but very efficient, also.