As soon as you exit the Pyramid, Star Master comes to take Poo away to teach him Starstorm. Once he's gone talk to the native to next to the Pyramid and he'll give the Key to the Tower. Head north of this man and you'll meet a man with a camel. He sells some really good weapons, so talk to him and buy them if you can afford. It is most important to pick up Paula's French Fry Pan here if you can. The Multi-Bottle Rockets are Jeff's best attack items in the game, but they are expensive so don't worry about picking any up right now.
Be careful you don't stay out in the heat too long because you can get sunstroke. Also, the enemies here are a little difficult and may poison your team. Head to the northwest and you'll come upon a large tower than looks like a man. Use the key and enter the most annoying dungeon in the game, the Dungeon Man.
Brick Road's New Dungeon
On the left after you enter is a bench which will restore your HP and PP completely. There is also a telephone and ATM nearby, and a hospital is through the cave entrance to the left. You'll notice that there are signs just about everywhere in this dungeon. Read them because some are quite funny. It is not essential to get all of the items within Dungeon Man, but this guide will explain how anyway.
The enemies on the first floor are easy. You might recognize them as the enemies inside the Fourside Department store, back when Paula was taken. You've gained many levels since then, though they should pose no problem now. Head to the right of the entrance and walk north. If you don't take any splits you'll come upon a present that contains Molokheiya Soup. Go back south and head to left at the first opportunity. Go north immediately, taking you up a slope to another split. Take a left at this split and you'll find a Cup of Lifenoodles. The right split leads to a bathroom and another sign, but no presents.
Backtrack and take a left once you reach the bottom of the slope again. You'll be forced to move north immediately, so do this and follow the path around. When you reach a split, go south. You'll come upon a present that contains $5 pretty soon. Head up the slope to the north of this present and take the first right to find a Snake in a present. Head back and take the northern split to find a Super Plush Bear which will be handle on the next floor.
Head back all the way to the south and take a left where you found the $5. You'll have to go north again almost immediately, which will lead you to four ropes. Thankfully, three of the four ropes lead to dead-ends so we only have to take one. The correct rope is the one that is second from the right.
The enemies on the second floor are more difficult than those on the first. The Lesser Mooks in this area can use PSI Freeze which can freeze your party and cause a lot of damage. Even worse is that they can diamondize you, one of the most dangerous status effects in the game. A diamondized character is essentially dead and if everyone on the teams is diamondize or dead at once, it's a game over. The Super Plush Bear will hopefully take the brunt of the diamondizing attacks.
Head south until you come across a split. If you want a measly $10 head to the left at the split and grab it from the present and then backtrack, otherwise just head south. Go as far south as you can and then take a left. You'll soon reach another split where you should take the northern path. The left path leads to another dead end (and a sign). You'll see a rope on the left that you should take.
Go to the southwest of the rope and then north a little to grab the Sudden Guts Pill from the present there. Go as far north and left as you can to get a PSI Caramel. Head back and take the rope up to the third floor.
Third and Fourth Floors
There are no enemies on the third of fourth floors, so you'll have a little break. The third floor is a zoo where you can look at Mad Ducks and Gruff Goats. You can restore your HP and PP on the bench which is in the south next to a Wet Towel. Find the rope that leads up to the fourth floor (it's to the north of the bench).
On the northern part of the fourth floor you'll meet Brick Road. Talk to him and he'll restore you HP and PP as well as heal your status ailments. Head through the first hole you see while walking south and continue to drop through holes until you reach the bottom floor. Make sure to grab the IQ Capsule on the way. Exit Dungeon Man and he'll now be following you.
If you get attacked while Dungeon Man is following you, he will be able to help out the team by attacking the enemies. Dungeon Man is fairly strong so use this opportunity to gain a few levels. You can re-enter Dungeon Man and rest up any time you'd like. Don't forget to save. Before you move on, grab some money from the ATM and make sure to buy Paula's weapon from the man in the north. If you have some money to spare, pick up a multi-bottle rocket or two.
The Yellow Submarine
When you are ready head to the south through the palm trees and Dungeon Man will get stuck. Head to the right and talk to the native who will say that you need a submarine. Return to Dungeon Man and head to the top floor. Speak to him and he'll let you use his submarine! Do not take the first hole this time. Instead follow the path around and take the hole at the dead end. Drop through some more holes and you'll reach an area you hadn't before. Grab the Talisman Ribbon to the south and then follow the path. Save at the phone and use the Revitalizing Machine if you need to. Check the submarine to continue on to Deep Darkness.