One of the problems aknowledged in this forums is that even though there's evolution in the "meta" part of the game, it happens maybe too fast for people to taste it. The jump from trial to standard to difficult dungeons is just in the length of 3 or 4 quests. Aside from your standard, hard but balanced random dungeons you could give a number of premade dungeons in each tier for new players to test their skills in. Where in Puzzle Dungeons there's only a fixed solution this ones would be a bit more open.
I know it is not the newest idea, but some indie games are trying to overcome this by lending your quick&dirty editing tools to proven people (not me!) (well, maybe I can give it a go but no promises!) for them to create some maps. Examples of games doing the same are Monaco, VVVVVV or No Time To Explain, and in a different way Super Meat Boy.
Just give it a thought.