I definitely had Debian installs pulling binary package dependencies automagically via apt-get in 1999, and I think similar with RedHat a year or so before that.

Though that doesn't cover much of the 90s.