What do you want to use it for? If you want a toy to play with or something you can set up quickly and have it automate things for you or something just to "sample", maybe try Redhat or Mandrake or something that's "easy". If you want to learn how Linux works and really have a distro you have control of and use well, Gentoo is the way to go. Gentoo takes a lot of time and effort to use and learn and set up in the beginning, but in the long run it's far easier to maintain, and it does the "hard" stuff for you while leaving most of the power in your hands.

I wouldn't really agree that Linux is far superior to Windows in every way for everyone. Some people want a computer to be a tool to use to get work done as fast as possible, and Windows is OK for that sometimes, if you don't mind a buggy piece of crap that doesn't work half the time. Some people want their computer to be a hobby, and Linux is good for that, because Linux takes a lot of time and effort, but what you end up with is something much more fun to use. Some people want something that's free because MS is a bunch of shysters, and Linux is good for that too, but only if you can get used to the many changes and quirks.

I'd suggest reading the install instructions for a bunch of distros and picking the "hardest" one you think you can handle. Gentoo is the only distro I tried that I managed to use as a total replacement for Windows, and it's what I use now. Gentoo looks hard to install, but the docs are very very complete and newbie-friendly. It also requires more learning, but to really use Redhat or Mandrake or something you'd have to eventually learn all that stuff anyways; Gentoo just makes you do it sooner.

As far as programming, you don't need to learn to program to use Linux, but it couldn't hurt. BASIC isn't going to help much though, no one uses BASIC. I did learn to program using BASIC myself, but that was 10 years ago, and no one even used it back then. It is good to teach you the fundamentals of programming, but I'd recommend Python as something that's as easy as BASIC, but also useful in the real world.