From what I have seen many of the comments against the system used in morrowind were about EVERY dungeon being either too easy or too hard. This idea may fix that somewhat.
Every location is given a Location Level, ranging from 1 - whatever the cap is. Then, when you enter the location, the enemies generated are the Average of your level and the Location level, so if you are a level 10 entering a location that is lv 20, the enemies you face will be level 15. This means that the locations suitable for you to visit at your level are doubled, difficult locations will still give you chance to run away and not 1-hit you, and areas below your level won't be as much of a waste of time.

Alternitively, you can change the weight that the player level has in what you end up with, for example, with a player level of 5 and a location level of 20, to have the enemies you face be level 10.

Not too shabby of an idea. The difficulty idea you have is pretty good, I like it.
Maybe even show the level of the character/dungeon, so you know how it is. They had that in Borderlands, and enemies that were a lot more powerful than you would have a skull next to their level, so you that they're dangerous.