Labyrinth is for me the 2nd hardest of the "hard" dungeons after Gaan-Telet. Not because of bosses (well, Rex a bit: "Crouch goddamnit! Stop blocking the escape route!"), but because unexplored tiles aren't a reliable ressource (unless you get ENDISWAL or got lucky with many possible paths), along with a very restricted choice of monsters to kill. Also, most of the time, it prevents you from reaching vital glyphs (the worst are linear "labyrinths" with an early high monster blocking 2/3rd of the dungeon).
I remember when I didn't know that Shifting Passages was a "revealing" labyrinth and I was using IMAWAL alot, making lots of closed space: I killed my first Evolvia spamming WEYTWUT (the boss should have died from throwing up). It was hell. Now that I "xp catapult" (still using IMAWAL
), killing very few selected monsters to reach 6-7, going for bosses when only half of the walls are put, it's pretty easy.