The summary of the paradox in the question seems correct to me as far as it goes. Zeno's proofs were presumably intended to support his master Parmenides' view that relative motion implies a background or source that is absolute stillness and changelessness.
The same argument is just as valid today, when formulated carefully, and it supports the view of time and change proposed by the perennial philosophy. If you read Nicolas de Cusa you'll see that he does indeed propose that things move and move-not at the same time.
I don't think Zeno knew this other philosophy well or he would have made more developed arguments. The idea is not that motion is impossible but that it is mind that moves, not intrinsically-existing objects (there would be no such thing).
Time and motion would be paradoxical only when we reify objects and space-time. If we follow Kant and de-refify them then the paradoxes evaporate. But we then have to say the things both move and move-not. They move to the extent they exist (as appearances) but for an ultimate view motion and change would be impossible, just as logical analysis proves.
A common Buddhist argument runs - change cannot happen in the past or the future and there is not enough time for it to happen in the present. Ergo it does not happen. For the experience or perception of change we have to combine past, present and future, and this can only be done by a mind.
You ask whether we are supposed to see his paradoxes as 'true'. It's probably better to say that we are supposed to see them as 'holding', thus proving that our usual idea of motion is metaphysically absurd.
The reason the paradoxes of motion (Zeno's or any others) are usually ignored seems to be that if they 'hold' then they render materialism absurd and lend credibility to the perennial philosophy. It is an odd thing that the philosophy of the mystics pays greater respect to logic than what Russell calls 'Rational' philosophy but it's always been this way.
This so-called 'Rational' philosophy cannot make sense of metaphysics because it ignores these paradoxes on the grounds that naive-realism (the wysiwyg universe) is true even it it is logically absurd. Zeno was trying to poke holes in naive-realism and so is not a popular philosopher among scholastics.
His goal was not "showing that "normal" reality is actually wackier than the reality posited by Parmenides." There is only one reality. His goal seems to have been to show that Parmenides was right, reality is a lot whackier than naive-realism would have us believe, and lot less paradoxical.