Lufia 2 was my favorite. Most first dungeons are your first slog through monsters to get the MacGuffin, but Lufia 2 did a little more than that. It was a tutorial for the unusual nature of all the dungeons of the game, where moving forward or getting the chests involved a little problem solving. The dungeons are half puzzle. It was also super short and had no boss, so you weren't overwhelmed with information and could get it out of the way and move on with the game, trying out what you learned in the next, more unstructured cave (the one I keep forgetting isn't actually the first dungeon). Lufia 2 is pretty good to look at for making dungeons fun overall, I think. I liked how the monsters were on screen, and were sometimes part of the puzzles. You could have cutscenes happen in them. Moving forward wasn't ever just "push A to win", you had to actually think about the best way to do things, in and out of battles. Being able to interact with the environment also opened up the possibility for secrets, which were always fun to find.
So, I think the takeaway is that the first dungeons should give you the information in the quickest way possible, then give you a chance to experiment with what you've learned. Dungeons should be part of the game play and narrative, not just a generic wander until you find the easy boss. Make it easy to come to a solution, but don't make them follow step by step instructions, let your players choose and think a little. Then, even if it's way too easy for an experienced and smart player, it at least won't be quite so annoying. I've found that humor can go a long way in this area, when it's just going to have to be simple, at least make it funny.