One of the more interesting parties I've used for that dungeon was Cyan, Mog, Gogo and Gau.
Mog dances. Gau rages. Gogo can Dance or Rage (If you've been collecting Rages, Rage is better, though Wind Song has a healing move which is nice).
Meanwhile Cyan has all the time in the world to charge up his swordtech. Quadra Slice(7) is fun, or Quadra Slam(4) if you're impatient.
That leaves Locke, Shadow, Strago, Relm, Umaro and Setzer.
Umaro stays on the airship. He sucks.
Relm's a good caster. She comes.
Locke can have a great equipment set up with Valient Knife, Atma Weapon and Genji Glove/Offering. He comes.
Pick the character you hate the most of Shadow, Strago and Setzer and ditch them. I tend to leave Setzer on the airship for thematic reasons, because I don't trust anyone else to fly the thing while we're down there.
(Edit: Setzer, not Strago, though I don't like Strago either)
