I kinda agree with Arky (yes, it does happen). Given the lack of a bitmap mode on the PCE, a platformer (or shooter, or other simple, sprite-blitty game) might be an easier start. That said, if you do the first-person dungeon in chunks, un-animated, it probably wouldn't be so bad at all. What I mean by that is instead of walking forward smoothly, you walk forward one square and your perspective on the dungeon jumps forward.
Has anyone managed to determine how Double Dungeons does its animated step-forward bit? There are other systems from that era which surely do the same.