- Versions of software included
    - Whether any "non-free" software is included
    - How the directory structure is used (for instance, do you use /opt or /usr/local)
    - Is there a package manager / ports system, or do you compile everything on your own?
    - In the event of multiple solutions to the same problem (common), the distro often makes a default choice
    - The GUI often has custom features, such as configuration applets
    - The support culture around each

Several distributions (such as Ubuntu and its derivatives) are moving towards replacing init and related scripts and tools completely with upstart or similar options (http://en.wikipedia.org/wiki/Init#Replacements_for_init).

Generally, the biggest difference between distros is that some come largely pre setup with all necessities taken care of out of the box with an easy install, such as Ubuntu, whereas others allow users to configure their operating system to the smallest detail and only provide the tools to help them do so, such as Gentoo. Generally the latter distros require more savy users and will require them to familiarize themselves with the more mundane differences between distros.

I think the most defining characteristic of each distro is usually the package manager or equivalent system. Also, the amount and quality of packages available for distro. Most major distros have their own and each determines a lot about the distro. Debian is known for apt-get for example (which Ubuntu borrowed) which is held in high regard for being relatively easy to use. Gentoo, however, uses portage, which is slow because it usually downloads packages as source and compiles them before installation, but provides a ridiculous amount of flexibility in configuring a system, right down to specifying the compiler flags packaged will use. Both of the these have large repositories of packages for users to browse and select from. Slackware, by contrast, has no package management system to speak of, but does have packages which you can download and install separately.

Yes. In practice, however, remember that linux software is usually manged through a package manager. This means each distro packages each software package to install using their own conventions and formats. Some conventions (such as freedesktop.org guidelines) and formats (both SuSE and RedHat use YUM/RPM) are shared between many distros, others are not. Also many distributions will patch software specifically for their needs and may even have different compile-time options enabled.

how large is the difference between base versions (i.e., debian vs. redhat)

There are differences:

- between how they handle software packages, like I stated earlier

- in QA and release policies (what RedHat considers stable and Debian considers stable might be different even for the same package)

- in security features (SELinux, grsec, AppArmor, ProPolice, etc.)

- in default packages installed (PCLinuxOS ships with KDE, Ubuntu with Unity, Debian with Gnome, etc)

- in init systems (Sys V, systemd, upstart, OpenRC)

- in available support options

- in release schedules and methods (rolling release [Gentoo, Arch, Foresight] vs scheduled releases [Fedora, Ubuntu] vs "when it's done" [Debian])

- Commercial (Ubuntu, SuSE and RedHat) or volunteer/nonprofit (Debian, OpenSuSE, Fedora and most others)

- in legal and "ethical" standards (nonfree software availability, availability of software known to be infringing on US patents, nonfree drivers or firmware, etc.)

There is an attempt to arrange things logically, so even if you're unfamiliar with the init system on a specific distro -- if you've worked on any other Linux (or even BSD) init system before you should be able to figure things out pretty quickly. Other things, like SELinux, aren't immediately intuitive if you're not familiar with them.

The biggest advantage of the Debian (and derived) distributions is that they have the largest set of prepackaged "things," which makes most things an "apt-get" away. This is very convenient, but not essential.

Back to your question, prepackaged "things" must be installed on the distribution that prepackaged it (you can "cross the streams" to some extent, but a cross-distribution install has a finite, possibly large, probability of not running).

If you are willing to build the "thing" itself, the portability is pretty close to 100% that it will Just Work[tm] with a "configure && make" build. For complex "things" with dependencies, this can grow geometrically into being a major effort to find and build all the dependencies.