First things first:
As far as Linux goes... I am a bit of a Newbie
However, I am looking for a distrobution to fit a complicated set of requirements, and could use some advice from some more experienced users.
First off, I need it to run on both my PCs, so I don't have to figure out distro differences all the time. Here is the specs of both computers.

PC1 - Homebrew desktop
> Asus Motherboard w/ integrated Ethernet/soundcard/usb (Need to disable this soundcard)
> 1.6 Ghz Pentium 4 processor (No Hyperthreading)
> 256 MB RAM [Gotta upgrade!]
> Visiontek 128 MB graphics card (ATI Radion based)
> Soudblaster Live! 5.1
> Linksys PCI Wireless-G card (brand new)
> Generic CDRom
> Generic Floppy
> IoMega 100 MB parallel Zip drive
> Wireless PS/2 keyboard
> Microsoft Optical Mouse (School threw it away, works fine!)

PC2 - Dell Inspiron 1150 Notebook
> Integrated intel 64Mb Graphics Card
> Integrated soundcard (Soundblaster Compatible)
> Integrated Broadcom Ethernet port
> Syntaptics Touchpad
> LCD 1024/768@65
> DVD-ROM/CD-RW

USB devices
> USB2PSX adaptor (gamepad)
> USB floppy drive
> USB flashstick-based MP3 player

I will also need a certain pile of software on the CDs, to minimize downloading. Here is a basic list

Known programs:
> Wine
> Gkrellm
> Bash
> Pearl
> Apache w/ PHP & MySQL
> Mozilla Firefox
> Mozilla Thunderbird

Needed stuff:
> Video Editor
> A lightweight GUI that just gives me a wallpaper, multiple command lines, Gkrellm, and a large command-line window.
> A video player that can play DIVX out of the box
> Dos Emulator

I am also learning extra languages, so any tools that can help me learn/are translated into German or Japanese would be very useful indeed.

I also want to make sure that the distro is not fully newbie-ized. This is a setup that I will be using (hopefully) for many years to come. Also, in the years to come, I will be getting my linux admin certification at the local community college

Oh, yes, and Distros I have already found and disliked:
SuSE (Everything is moved around!)
Redhat (Way too newbieized)
Mandrake (SLOW)
Debian (Got stuck with a command line, and barely any hardware working)

Great thanks to anyone willing to help me with this.

Things like a DOS emulator and divx probably won't come with the distro and will need to be setup, end of story. Why do you want to mimimise downloading? If you choose a distro with FTP install you get the newest packages which means better hardware support and better features.

I'm not sure here but I reckon you'll have problems with your gamepad, all the rest of your hardware looks ok but the ATi-based card has crap drivers, expect poor 3d support. And it's Perl, not Pearl

Even though you say not much downloading I'd still say Arch Linux, it's very configurable but picked up all my hardware fine and you will have to learn to get it installed. It's like a newbie gentoo, you don't have to bootstap your system or compile your kernel but you do just get dropped at a commandline after a net install and you go from there. Unless you're on dial-up or have a valid reason to want to not download in which case DamnSmallLinux (can you install this?) might be a tad better, or the minimal Slax version, I'd say Slackware but if you struggled with Debian then Slackware probably won't be any easier.

Slackware might be nice... if I could get pointers to a few good setup guides.
Also, is LFS a viable option? It seems kinda interesting, but I don't want to spend several months setting up the computer.

PS: I can't spell to well.

If you don't want to download much and you want all the stuff you said preconfigured and you want any sort of automatic hardware recognition at all then LFS isn't an option, not even close.

And did you look at the Slackware site? This seems pretty good, never used Slack myself but this book seems pretty comprehensive

By download much, I mean downloading after installation. Kinda frustrating to set up a distro, and download pretty much every program you need.

I'd still say use Arch, once you have it setup then this is how you install stuff, and it's really fast because everything is optimised for i686
and then you update you entire distro and all software packages installed with this

Oh, wow, that is simple! I'll take a look at arch!

Oh, beautiful... Just realized that I ran out of blank CDs. Sonofa...

I reccomend MEPIS

it seems like you are really looking to get into linux. Also with all of your requirements it might be good to use lfs. It will take some time to set up but should work well. For the base distro you might want to use gentoo, a high customizable distro.

With some of that hardware I really don't think LFS is a good idea just yet. Maybe later down the track but not right now...