Let This Be Your Last Battlefield.
Being black, I never understood why most people's interpretation of this one generally tends to limit it to race. It's about more than that. In my view, the episode works better as a metaphor of the Israeli-Palestinian conflict of the past decade if anything.
The last lines stuck with me the most:
Spock: All that matters to them... is their hate.
Uhura: Do you suppose that's all they ever had, sir?
Captain Kirk: No. But that's all they have left.