Debian and Mandriva both have full install disks in addition to network and/or liveCD install disks. Debian's is around six DVDs or something like that but you get the full repository library.

Debian also has the apt-zip package which can be used to download packages from the official repositories using a fast connection then walk them over to the slow connected machine on disk.

Network install and repository managed is preferable where possible but it's a good idea to confirm if the desired distribution has a full-install version with fully stocked disks.

(A week hunting dependencies for VLC.. yikes.. A few of the regulars here may have been able to help reduce that install time)