To make the mayor unlock the path to Giant Step, you defeat the Sharks gang.
Talk to the Mayor
After you defeat Frank, talk to the Mayor to get the key to the traveling entertainers' shack. Before you go into the shack, talk to the guys wandering around outside the shack and one of them will give you the Travel Charm, which increases your defense.
Prepare for the Cave
Be sure to have some food in your bag before you go into the cave. You will need it if you run out of PP to heal yourself.
Go Through the Cave
Go through the shack, then enter the cave. You will encounter Attack Slugs, Rowdy Mice, and Black Antoids in the cave. When fighting these enemies, heal up if your HP is 15 or lower. When fighting Black Antoids, attack the Black Antoids first if there are other types of enemies, because Black Antoids can call for help. Keep in mind that Black Antoids can use Lifeup α.
From the entrance of the cave, go left. There is a room along the way that contains a Skip Sandwich. This heals you up about as much as a Cookie, but it makes you walk around twice as quickly.
There is a rope that leads up to a higher level of the cave, and beyond it is a door, but the room there is empty. The second level of the cave is straightforward: just go to the right from the rope. Eventually, you will find a rope to the third level of the cave. Just beyond that rope, there is a room that contains a Cold Remedy. You are not likely to catch a cold at this point in the game, but you should save this item for later.
The third level has a door on the far left that goes outside. Go out there to find a Magic Butterfly. The butterfly is likely to reappear if you go inside and outside again. Use this to heal up all of your HP before you continue.
In the next cave area, there is a gift box containing a Hamburger. Go through the door at the top.
Defeat Titanic Ant
Eventually you reach a room with a series of ropes going up. At the top of these ropes is the boss of Giant Step.
Titanic Ant can use PSI Magnet, so you will probably run out of PP before the end of the battle. Keep in mind that the Skip Sandwich does not restore very many HP, so you should not use it during battle.
There are two Black Antoids next to the Titanic Ant. They can use PSI Lifeup to heal the Titanic Ant. They will run out of PP after about five turns.
Titanic Ant can cast Shield α, which will reduce the effectiveness of your physical attacks.
Use PSI Rockin α on the first turn if you have it. This will kill the Black Antoids immediately. After that, you might want to only use PP for healing.
Get the Melody
After Titanic Ant is gone, you can go through the door to Giant Step. When you approach the giant footprint, your Sound Stone will record the melody of the place.
Go to the Police Station
On your way out of the cave, the monsters here will all run away from you. When you exit the cave, a police officer of the Onett Police force will tell you to come see him at the police station. It sounds like a trap, but you have no choice.
If you are below level 7, try to level up before continuing on.
In the police station, talk to Captain Strong. Say yes when he asks if you really want to go to Twoson. He will lead you into a back room where several police officers will attack you! Police brutality!
You will have to defeat a total of four cops (the fifth one runs away). You can't heal up between battles, so be sure to heal yourself during the battles. The cops can use a Crushing Chop, which damages you by about 25 HP.
After defeating the four cops, Captain Strong attacks. Keep your HP above 50. Use PSI Rockin α or regular attacks, healing up with food or Lifeup α, until Strong is defeated.
After you have defeated them, Captain Strong will radio the officers who set up the blockade to the south, telling them to let you through. Now you can go south to Twoson.