Underworld Adventure Encounter, Puzzle, Riddle HELP

Going to "Yes, and..." this but an important consideration is the appropriate level for the setting. Just like 4th levels aren't slaying many dragons, the most skilled fighter in a small town (~2000 population) isn't likely to have an underworld adventure. Typically planar travel is a "you must be 10+ level' to ride, so I would recommend avoiding any meeting with Lords of the Underworld-- they quite simply have better things to do.

Onward!

I particularly like the Chase mechanic from Pathfinder--
Chases
That link has everything you might need to block & plan an action packed scene. I think you could stage it in the traffic or a marketplace somewhere; one macabre detail from D&D cosmology is you will typically find a market dealing in the value of souls somewhere or another in the afterlife.

This is a low-fi blog from 2005(!) that is really focused on the Planescape setting.
Pathguy
Back in 2E Planescape was entirely based on the outer planes. The D&D Outer Planes are all connected at some point or another and all border the Borderlands (cute, right?). Anyway, that blog in particular has a theme around using the Outer Planes as a framework for ministries-- I think all of the characters were missionaries and the games were run intending to explore philosophical underpinnings of morality, etc. In your case I think the cleric should have a special role to play, as they should have a relation to some part of the underworld.

As far as riddles, you can always go classical and study Dante's Divine Comedy. It's basically the story of one fellow walking through all the layers of Purgatory, Inferno, and Paradise. They're all connected after all, and there are even classical illustration of the sorts of beings you'd encounter.



Jean-Edouard Dargent - Illustrations from Dante's Divine Comedy

Hope some of this helps. There isn't anything special about riddles, quests, or tasks in the underworld, not really. Just throw typical challenges at your players with otherworldly flavor.

Brief P.S. -- Is the Goddess of Birth, Healing, Death three beings? Or one being with 3 aspects? You say the goddess of death is both a fan but hates the songs, so it's a little confusing. I like the 3 aspects, reminds me of the deity who aged every day from Dawn to Dusk, reborn anew each day.

Thanks!  The party is now in the lowest level of hell with the Assimar Bard was recording the life history of the goddess of winter (she spends the summer down in the coldest level of hell).  The party traded her a book that writes everything you speak to it (ingenious idea) for the soul of the bard.  I see your point of them being too weak to spend much time down here, so I like your idea of they need to either only explore/escape from a single level or they need to evade notice of the more powerful beings the entire way up. Lest they be given impossible tasks by the demi-gods/minor gods that rule down here.  I am thinking perhaps the goddess of death shows them a secret way out at some point.  I do want them to get to the next level up where it is a modern city version of hell.  Perhaps they need to go to the soul market in the city to find a merchant that can sell them an artifact that will open a secret portal?