A large peninsula stretches west past Melmond and contains the next several destinations in your quest. It's unclear based on the hints in town whether you need to head for the Titan's Tunnel or the Earth Cave first. Either way, you're going to need to cross terrain filled with some dangerous enemies.
The most common encounter in the area is frustrating, but manageable. You'll continually see large groups of SHADOWS, and they will frequently gain surprise. As in the Marsh Cave, they will hit you for minor damage but inflict Darkness, which serves to prolong the fight. If you want to avoid wasting time, you can probably spare a level 1 spell slot to thin their ranks with HARM.
The groups of GEISTS that you saw in the Marsh Cave area have been augmented with another Paralyzing Undead, the GHOUL. GHOULS are not as dangerous, but the combination in large groups can easily lock down your whole party with Paralysis.
Aside from a rare encounter featuring ARACHNIDS, none of the other monsters you'll fight here have any fancy tricks. TIGERS appear infrequently, and have a high chance of dangerous critical hits, but are otherwise reasonably similar to GrOGRES, which also appear here. HYENAS are of the same ilk, though they lack a special critical hit rate.
As you travel west, eventually you will come upon a narrow pass between a pair of mountain ranges. An isthmus to the south leads to a triangular land mass where you will find the Earth Cave. If you instead continue west, you'll reach the Titan's Tunnel.
Titan's Tunnel (Optional)
There is nothing to find here at this point, but you can speak to the Titan if you want. He won't let you pass until you bring him a RUBY. You'll find more TIGERS in the Tunnel, but no Undead. This isn't a bad place to earn experience, though you'll find slightly more gold per encounter on the overworld. The Earth Cave is much better than either, but it's also more dangerous.