Are you focusing mostly on roguelikes? Unfortunately most roguelikes tend to be purely dungeon crawling with little story, but there are plenty of games with roguelike elements, or even commercial roguelikes that could work.
The mystery dungeon series can be quite fun, and there is a wide variety to choose from. Shiren the Wanderer is generally the favourite of them, although there is also all the pokemon ones, if you're into that
The mystery dungeon games are on plenty of platforms, including some easy to emulate, if you wish to try before actually investing in any. Similar to those is the two Izuna games for the NDS, which are the type of games that some people love and others hate.
The best other example of a game that could work is Zelda games, which tend to be open world adventure games focusing around dungeon crawling, but usually with a storyline. I recently reviewed two Zelda Classic quests, which are user made Zelda games using the Zelda Classic engine, for my site, both of which were quite fun. End of Time DX has little story, but Lost Isle has story to it as well as a massive overworld to explore, with secrets everywhere. There's hundreds of quests available for Zelda Classic, so you can always look to find some good ones. Another two popular quests with storylines are Light of the Heavens DX and it's sequel Darkness Within, although I haven't personally tried them yet.
