Transfer all characters on two or more light population servers into a new server and give every character and legacy a free rename.
Notification of merges should be sent out clearly in advance and perhaps players should be given the option to transfer early via a paid transfer. (to maintain dibs on legacy name)
I think this is a fair solution to the character name and legacy collision problem.
Personally I would sort of enjoy renaming my character. This is a paid for feature in other games.