With Randall defeated, turn and head to the East again, and you can pick up a Protein.  Return to Randall and head South until you can resume going East.  The path here nudges South slightly, to a Strength-shovable rock and a hiker. 

Battle: Hiker Keith (992 Poke)
Opponent: Drilbur Lv 31, Roggenrolla Lv 31

Follow the path East to the 'door' leading South and you'll find yourself in a damp area with some water.  Keep that in mind, as you haven't gotten Surf yet.  Head East after descending the stairs and you'll find another mountain man.

Battle: Hiker Tobias (992 Poke)
Opponent: Roggenrolla Lv 31, Timburr Lv 31

Continue East from here straight and ignore the South branches of the path- instead shove the rock ahead into the hole and cross over.  Bypass the North branch here to instead turn South and then East again.  This will let you head North via a narrow path off to the East edge of the cave and shove another rock into a hole so you can cross.  First, though, you'll have to contend with a Psychic.

Battle: Psychic Ena (1024 Poke)
Opponent: Baltoy Lv 32, Yamask Lv 32

Beware of Ena- her Baltoy will Selfdestruct if brought to the red and given half a chance, and her Yamask likes to open up with Will-o-Wisp and then make things worse by afflicting you with a Curse.  After defeating her, swipe a Red Shard off the rock to her left, then resume heading North.  You'll find a passage that leads into the lower parts of Relic Castle.

Travel East through the only open doorway and again across the room you find there to enter a room with four vases on the North wall.  Pause in the middle of the room and scrum about and you can rummage up a Sun Stone, which is used to evolve certain plants (primarily Sunkern in this game, though it also helpfully turns a Gloom into a Bellossom).  Head North from here and you can enter a room where Volcarona, the Fire/Bug moth is waiting for you.  Talking to Volcarona will start a fight that you may well not be ready for- the thing is level 35 already, and is a very powerful pokemon regardless of level.