The biggest mental leap from classical mechanics to relativity is getting over the concept of universality - that time, space, and everything in them are not the same from everyone's point of view. There is no universal "now." But there aren't paradoxes, actually. One of my favorite ones is a guy running into a 30ft barn with a 30 foot stick at 3/5c, and once he's inside, the barn door closes behind him. The guy sitting in the barn says he fits - the guy and the stick are length contracted and the barn stays at 30ft, so he fits in fine. The running guy says he can't fit - he has a 30 ft stick and the barn is length contracted shorter - there's no way he can fit. Even if the 2 observers can't agree on the length of the stick, they have to agree on whether or not it fits. You can't have one person saying the door closes around the stick and one guy saying the door can't close - they have to agree on this event. Can you figure out who is right and why?
It's a little wacky at first, but understand that concept and a lot of relativity falls in to place. The solution to this problem isn't math intensive, but it's beautiful. There are books that explain it far better than anyone in this thread, so I suggest reading about it.