For the impatient, though ( :P )...
A lot of the problem with understanding Relativity probably comes down to the fact that most people don't really understand how motion works normally. I mean, intuitively they do, of course, but that's not really the same thing. Putting intuition down into concrete mathematics helps us to explore that intuition and understand its consequences better.
Another point is that our understanding of physics often relies on asking the question "what never changes no matter what I do?". Hunting for things that can be reliably constant is a huge driver of modern physic, but at High School it feels like almost a footnote. People come across the "Law of Conservation of Energy" (or momentum), but it feels like it isn't really explored. Which is a shame, because it's huge in its implications -- it turns out that there is a direct consequence of that statement that can force any theory to have a certain form.
I'm wondering off-topic, and anyway I have to hop out again for a few minutes. But part of my answer below will be trying to expand on this point: for all that Special Relativity is about how times and lengths change, it really *is* true that the heart of the theory is about what doesn't change, and why that might be.