OK, here are some of my ideas:
Wilder encounters in wilderness:
There was some talk about people not knowing how the background corruption rate in wilderness increases. What I propose is to SHOW them -- by adding new wilderness encounters or altering the old not limited by level, but by elapsed game time.
The chaos encounters would grow in both frequency and difficulty, the number of chaos brothers and sisters in pilgrimage, say, would have a new term dependent on time. Writhing masses of primal chaos would start to appear from day 90.
Chaotic quests: some minor chaotic quests, so minor that the PC might not even know what they are for. Perhaps a quest to exterminate a herd of blink dogs? The damage dealt to Law would be minor, but sufficient to, say, pull the date of background corruption increase back a few days.
Moral UE: not requiring character to change their alignment. Was mentioned here before.
What's the main problem with alignment change? That you have to be chaotic to satisfy Gaab'Baay's quests. What if I don't want to be chaotic, though?
Possible solution: have Khelavaster (once saved) function as a quest-giver to provide an alternate way to get the Crown and Medal. This would be, of course, harder then the regular route, but the character could be rewarded by, say, getting a "never once stooped to Chaos" on his win file.
The alternate way:
Demented ratling -- he knows the location of Stone Circle, but won't talk to L/N characters.
Solution: Cure him. Instead of six artifacts, throw six (or even more?) potions of cure corruption on him. After one, he becomes hostile, of course. But if you persevere, he will collapse, becoming a "dying ratling", and when you talk to him, he will thank you for saving his soul, whisper his terrible secret to you and die.
As a bonus, if the savvy character tries to give HIM an AoLS, the ratling will just chuckle, saying "Keep that. Your life is worth more than mine."
Alternately, this could be combined with the "six artifacts" requirement in some way. Or perhaps ordinary PoCCs are not enough and you would have to get a special artifact version from somewhere.
Gaab'Baay: She has Medal of Chaos, but will only give quests to C.
Alternate solution: Kill her. Khelavaster would give you the quest to do it.
However, if you kill her, you won't get the Medal right away. Instead, you'll find a note on her body noting a location of her house.
The house would be in the forest somewhere, not appearing until you get the note. It's (what else?) standing on a chicken leg. The surroundings of the house has some dangerous animals like bears and giant boars. The inside has the Medal guarded by the witch's familiar: a black cat.
Yup, to get the Medal this way, you'd have to kill a cat
The previous GB's quests could be mimicked by doing something equivalent to Khelavaster before he tells you to kill the witch.
Postgame quests: something to do after winning the game. Here, one of my old ideas: Reclaiming the ID.
1. ID will be (since gate is closed) non-corrupting. However, whenever the PC goes down, a "mouth on the wall" special room might be generated, telling some tidbit about the ID.
2. A guardian can be found on an unique level below, say, 50. Let's say that he has 1% chance to appear on 51, 2% on 52, 3% on 53, and so on. If he won't appear on certain level, he never will -- you'll have to get lower.
3. The guardian (infinity guardian?) tells you that the heart of dungeon is corrupted. He cannot fix it. He'll test you, claiming that if you can't defeat him, you'll have no chance against the rest.
4. After defeating him, a gate appears. You'll also get the Infinity Compass, an artifact amulet.
5. Going through the gate will throw you into next part of ID.
6. This place still DOES have background corruption and high monster generation. Cavernous levels are common. It's characterized by highly random monster mix and can include monsters that are normally limited to certain areas. Grues of all types in one place. Jackal demons. Some never-before-seen monsters, as benefits the idea of "bonus dungeon". Weretigers. Ancient quicklings. Karmic rats.
7. Level is only marked as ????. Multiple staircases, both up and down, are generated on every level. Only one will move you closer to the "heart", others won't change the distance or even increase it. Once you ascend or descend a staircase, you'll appear on another level, but the staircase will be gone.
8. The only way to find the right staircase, apart from blind luck, is to equip the Infinity Compass. When standing on the right staircase, you'll see a message "The Infinity Compass on your neck tugs up (or down, depending on the staircase).
9. After passing a number of levels, you'll get to the Heart. The Heart is in the middle of the level in a large circular room. When you get close enough, a monster appears on EVERY square in the room (so you can't easily retreat to a corridor and teleportation is, of course, disallowed). Anything possible or impossible can randomly appear here, including unique NPC's that died by your hand. (Kranach laughs. "I seem to remember that our last bout didn't go so well... you won't be so lucky THIS time!"). If you approach the Heart (after defeating all of the monsters or just after fighting your way in), you find that the Heart looks like a large gem. Suddenly, it inverts, becoming concave, a gem-shaped abyss. Throw the Infinity Compass in.
10. You'll find yourself on ID:1. Get out. Quest complete.
11. If you revisit ID, you will find a circle which will teleport you to any floor of your liking (up to a limit, lower floors can be unlocked). No purpose to it except for fighting stronger and stronger levels. Special features like vaults or herbs could now appear.
12. Completing the quest with any character would unlock a new option at the beginning of the game, allowing you to start a new character and going just through the "restored" ID without access to the rest of the game. Similar concept to "Ancient Cave" mode in Lufia II.