Hmmm. Have you considered maybe having a selection of unique spells (or just buffed versions of current spells), that a character can only have one of, and is randomly assigned to your potential choices? This would each character unique, make death feared (as there's no guarentee you'll find another character with the same buff) and shape play style.
Alternatively (or in addition to), each character could be random in their:
> Unique spells/ buffed versions
> Unique gameplay stats (e.g. jumping, detection)
> Resistances (e.g. to certain spell elements/melee)
> Other random effects (e.g. automatically be able to breathe underwater, resistant to wind storms etc.)
Just some thoughts