You know, although I've avoided damage scaled with level, I'm beginning to think I might allow it for critical hits. Fighters (and only Fighters) do double damage on a 20 that hits, or on any hit that’s 4 points above the target number. Heroes (level 4+) do triple damage, and Superheroes (level 8+) do quadruple damage. It's more restrained than the other scaled damage suggestions I've seen and keeps the extra damage from becoming routine.
It also raises the question of Fighter variants that do something else on a critical hit.