Indeed, the "relativity of simultaneity" is the key for an understanding of all the apparent paradoxes, people (including students!) seem to like. I also thought for some time, it's better not to start relativity with a treatment of all these "paradoxes" (including the twin paradox, the train example, ...). So I started with the usual "two postulates" (the special principle of relativity which is identical with Newton's Lex Prima, i.e., the existence of inertial refference frames, and the independence of the speed of light from the velocity of the source wrt. an inertial frame), introducing Minkowski space with its pseudo-metric and derived the Lorentz- (Poincare) transformation between inertial frames and then of course depicted everything with Minkowski diagrams (with the hyperbolae for construction of the unit lengths in different frames, emphasizing to forget about our "Euclidean Intuition" when reading these diagrams). Then you can do physics, including point-particle mechanics and classical electrodynamics in covariant form and avoid the discussion of all these kinematical paradoxes.
However, the students (and they are students aiming to become high-school teachers) pretty soon asked about all these paradoxes, because the wanted to understand them, because in the usual German high-school texts, of course, these paradoxes all occur and they have to teach them. So I included some of the paradoxes in the problem sets accompanying the lectures and make them draw the corresponding Minkowski diagrams. My impression is that this works pretty well, and the Einstein's train example (in different forms) is not at all bad or confusing but it emphasizes that the explanation for all the apparent paradoxes is that one tends to forget about the relativity of simultaneity. The most loved paradox is the "garage paradox" with a car "fitting" or "not fitting" into a garage, depending on the view of either the driver or an observer at rest relative to the garage.
I think the key is to first explain Minkowski space, including the pseudo-metric and then discuss the kinematical paradoxes as an application which can be depicted nicely in Minkowski diagrams. It's also helpful to stress that we don't "see" the length contraction, because length contraction occurs when measuring lengths, while what we see is determined how the light from the seen objects reaches our eyes.
