Linux is Linux under the hood. There are two major sets of filesystem hierarchy, though: one is used by RPM-based distributions, because they model their filesystem hierarchies off Red Hat, and the other is used by "the rest", and is a more traditional unixy approach to filesystem hierarchy (which means it's simpler, cleaner, and easier to understand when browsing through it the old-fashioned way). There are also three different types of package formats: .rpm, .deb, and "everything else". The .rpm packages tend to be very distro- and version-specific a lot of the time. The .deb packages are very portable between Debian-based distributions, as long as a given distribution hasn't played silly buggers with things like filesystem hierarchy or with permissions handling (think: Ubuntu). Anything not using .rpm or .deb files is probably using something unique to that distro (or small family of distros). Often, a given package type is not compatible on a distro that uses a different package type by default. Often, software that is not very well configured doesn't install properly on one distro when it was designed for another that has a different filesystem hierarchy.
When people complain, or in general discuss, "learning" a "new distro", what they're referring to mostly consists of the following:
dealing with the compatibility issues in using closed-source or half-baked software that was targeted for only one distro
dealing with differences in how package management is handled
dealing with the fact that sometimes you have to search a little harder to find where a particular configuration file might be hidden
Once you get familiar with two or three very different Linux distros, you'll have an excellent grasp of how to find stuff even when you move to yet another very different distro because, though they're very different from each other for Linux distros, they're still more alike than two Windows releases (let alone the differences between Linux and Windows). When we who've used Linux a lot complain about the differences between distros and talk about learning a new one, we're talking more about edge cases than core issues of moving from one distro to another.
Ultimately, the biggest difference you'll see between distros will be the default window manager and the way the installer looks.
The new debian-installer does provide a means for installing a default GUI setup, by the way, so you don't [b]necessarily[/b] have a lean install of almost no software. I do recommend doing a lean install and only installing software as you need it, using "apt-get install", however. The apt system is the slickest, simplest, easiest package management system I've seen, and makes it not only possible but absurdly easy to start with a near "bare metal" install of Debian and build from there without any problems. It's the "best" (in my opinion) way of getting exactly the system configuration you want, no more and no less.
I'm not a fan of the "install everything and figure that means you have what you want" methodology. I don't need or want "everything". I just need and want what I need and want, and I very much want to not have a bunch of unnecessary cruft. Thus, I'm a fan of Debian.