The problem here is with your axiom:
" Integrity is not whether you follow rules other people made"
While this is true, that is **not** what legalism is. Legalism is the strict adherent to an ethical "formula", it need not be another persons rules, if you have a strict set of personal rules and follow them without adapting for the situation in a formulaic way, that is legalism.
Yes you can have too much "consistency" in your application of internal moral rules. A healthy level of integrity is one where you **do** change your ethics (not formulaic) for the situation in an attempt to improve your morality.
You might have a rule "never kill someone".. But then if you refuse to kill someone even though they are about to kill 1000 people, then that would be "too much integrity" or legalism, following your personal moral code too strictly without situational awareness.