Don’t you think that the result of calculations shouldn’t depend on aspects of the implementation and in particular,
FullSimplify[-Re[x + y], {x, y} ? Reals] returning -Re[x + y] should be considered as a bug and fixed?
A ComplexityFunction based on the StringLength of the expression (perhaps with heads reduced to a single character) might be a more intuitive measure of complexity.