I'm sure the idea is not new, but will throw it in anyhow: how about some randomly generated quest areas? There are plenty of games now that work with this, without necessarily throwing out all story telling. Linear and carefully constructed dungeons or areas will of course exist, but to avoid it always being the same, some areas might enjoy some clear randomized aspects to keep the challenge similar, but with a degree of freshness all the same.