As always, it depends on who you ask. For instance, I work mostly on my laptop, so I tend to lean more towards minimalistic distros (Arch, Slackware, Gentoo). I'm trying to force myself to be more comfortable without a mouse, so I installed i3-wm (a lightweight tiling window manager) on arch, instead of the more heavy duty gnome/kde.
If you're completely new to linux then I think the popular answer would be to start with Ubuntu or Mint and start pokin' around. Familiarize yourself with the CLI, learn an editor (vi comes with most distributions). After learning your way around and getting comfortable on the command line you'll be in a better position to choose what's important to you and search out a distro that suits your purposes. It is unlikely that you'll want to stick with ubuntu/mint as you progress, but the installs are straightforward and will get you a working internet connection, editors, X, and all the bell's and whistles that come with gnome/kde. Wubi will get you started from inside a windows environment, or you can easily create a usb install disk.
There are so many options out there, and it's all going to come down to preference. Knowing what you want/need is going to come with experience. Start simple, and get your hands dirty, then pick the tools you need.
In response to "Where to Start?" questions, in terms of linux, ubuntu is probably the most common answer given, and not without reason. Everything you are going to need to get up and running is going to be there, following a rather straightforward graphical installation process. A popular internet browser, graphical network and hardware configuration tools, and an impressive software center for downloading packages come default, not to mention a giant community of users where most questions have already been answered somewhere on the web.
While the CLI/bash is indeed the same for nearly every distro, it can be daunting for a new user to be faced with nothing but a command line. IMHO having a terminal open in gnome next to an open browser with a tutorial or at least google, is a much more productive learning environment than the CLI of a fresh slackware installation.
On the other hand, it is for some of these reasons that some users choose not to use distributions like Ubuntu/Mint. These kinds of distributions can be referred to as "transition distros", because nearly any linux newcomer can run a default install and find what they need. These needs are satisfied in the way of software (packages), so a please all distribution comes with alot of software that an individual user may not need. Products like gnome and kde come with lots of dependencies and consume lots of resources.
The more minimalistic distro's that I referred to (arch, gentoo, slackware) focus more on a core system without all the extras. The defaults are pretty much only what you need to get up and running. This approach can allow for extensive customization based on user preference and system resources. Being able to build my system from the bottom up allows me to remove some of the fluff that is going to consume resources on my slower machine. For instance, Gentoo's approach to software management (portage), downloads a package's source and unpacks, compiles, and installs it. Through the use of USE flags a user can specify which features a package should support. For instance, on my laptop I use neither gnome nor kde, so not only would I not install those packages, but I would disallow support for those environments in my other packages. Distro's like this come with a much steeper learning curve, and tend to require some unix knowledge to get going.
In your first linux system, you should be looking for:
A simple installation process, that will get you up and running and learning in a short amount of time with minimal hassle.
A package manager that will make it easy for you to find the software you need and handle dependencies.
An environment that will suit your system and preferences, whether it be full fledged guis like gnome/kde or X with lighter weight dwm/awesome/i3.
As mentioned above, stability. Which comes not only from the distribution, but also from the quality of configuration.
An environment that supports your learning the basics. While a server could be setup on a gentoo box with a custom configured kernel (though some may discourage it), this would probably not be an environment conducive to your initial phase of learning.
Many linux users float around distributions so often that it is unlikey you will pick one to stick with right away. The important thing is to quickly build a foundation on the fundamentals that will ease this floatation and help you make informed decisions. Please know that I am not trying to promote any one distro in particular, but mean only to support your learning process and help you get started in a way that encourages you to continue participation in the linux community. I apologize sincerely if my original post, or this edit, are vague or miss the point of OP question.