This quest, while not the most difficult in the game, is certainly the most complicated in the sheer number of places that have to be visited in order to complete it. You start in Shamirik, where you get the quest to go talk to King Vothkaro of the Troglodytes. However, you need the permission of two people before you can even begin the quest. First you have to bribe ot threaten Supervisor Levin, and then you need to complete a mission for Commander Corrie. To complete the mission for Corrie you must first go to Softport and speak to Nydia about the Ritual of Sanctification. Nydia will then send you to the Hermit's Hut in the mountains north of Softport. Once you've learned the Ritual from the Hermit you must then go to the Troglodyte Altar, which is east of Angel's Rest. Then return to Shamirik, tell Commander Corrie you've completed her quest, and finally Mayor Knight will give you the quest to go talk to King Vothkaro. When you arrive at the Troglodyte Castle, King Vothkaro will give you a quest to kill Ellhioc, in the catecombs below the Troglodyte Castle. Upon completion of that quest Vothkaro will give you a quest to bring down the barrier separating the Troglodytes from their ancient enemy, the Giants. Unfortunately, to learn the location of the tunnel where the barrier is you have to go to the home of the Giants. So return to Shamirik to get your reward, then head up to Lorelei to begin the Giant portion of the quest.
In Lorelei speak to Commander Bruskrud who will give you a quest to free several prisoners and bring back the possessions of some dead soldiers. So now you head to the Giants Home. This dungeon consists of three levels, and you should really do all three of them at once. But on the bright side, you'll get the map to the Concealed Tunnel to bring down the barrier. So return to Lorelei to get your reward from Commander Bruskrud and then head off to the Concealed Tunnel.
Once you've completed the Concealed Tunnel you'll have completed the quest, and should now return to Fort Emergence for your reward, take your evidence to Berra and talk to Anaximander, and, since you should have talked to Sandra by now, go to the Bunker and get them to begin on the special weapon if you're sure you know who's behind the monster plagues. Then to the Tower of Magi to get your reward from X.
As I said at the beginning. A very complicated quest. I'm glad the harder quests aren't as complicated.