It's correct that you needed eight tanks which was pretty much impossible for many guilds... imagine a 25man Boss nowadays that needs 6 Tanks which alone would be a problem even with dual specs and 5 classes being able to tank. Only WARRIORS were viable tanks back then!
The fight as such wasn't so terribly complicated... once you figured out after what debuff-stacks you need to rotate you just had to not fail.
Kel'thuzad was definately harder except for the said fact that you needed eight warrior-tanks. He had sooo many deadly mechanics for a classic-wow encounter while needing massive amounts of DPS and HPS.
Hard to say which was the hardest encounter AT THEIR TIME because Naxx 40 was open just for a quite small amount of time and many guilds couldn't even try the bosses.