I remember using Mandrake (later Mandriva) - it also used rpm. Dependency hell was an issue there too; it probably had to do with state of rpm more than the distro itself.
Dependency hell was a thing for sure. I had at the time made a script to easily install rpm's at with a shell script that was searching the mirrors. It didn't handle dependencies but would show what was missing. But so many years later now looking back, a big issue was really just a lack of understanding of rpms with all the other os's with rpms, different arcs and versions. yum was a welcome changed especially since apt had for so long solved dependency issues.
