It's not a Giant on screen, it's the enemy Giant that you encounter in random battles. The area that they are talking about is located to the west of the stairs in the first level of the Earth Cave, where the path makes a sidways "U" (Map).

Also, the cave you are in with the "Giant" is called Titan's Tunnel and the "Giant" is the Titan. You want to go to the Earth Cave, which is southeast of the tunnel.