One of the most effective ways of convincing yourself of this is to contrast motion through space with motion due to the expansion of space. If you're an observer watching someone whiz by at .866 times the speed of light (.866c), then you'll see the second hand of his watch ticking off the seconds at half the rate of your own. But if you observe a watch in a distant galaxy receding from us at the same rate of .866c then you'll see the second hand ticking off seconds at the same rate as your own.
Caution... if you speak about what is "seen", then actually you do see the second hand ticking more slowly. Suppose a photon leaves the watch at a certain instant. Another photon leaves when the second hand has ticked off another second. The second photon has further to travel than the first, and so arrives more than a second after the first. You see the clock ticking off seconds more slowly.
In fact, this is one of the lines of evidence that redshift really is due to expansion of space, and not due to loss of energy by some tired light effect. Supernova light curves have a characteristic decay time; but those which have a high redshift decay much more slowly. This is due to the same slowing effect as with the watch.
You also get a similar effect with recession due to local motions in space, and for the same reason. Photons leaving later have further to travel, and take longer to get here. This is actually a reasonable correspondence over small scales (small in comological terms!) but this does break down over billions of parsecs.
Redshift can be seen in this way as well. A photon is emitted with a certain frequency. We see it "slowed down" (reduced frequency) which is the redshift.
One thing to bear in mind that in general relativity, notions of distance and of velocity over large scales are not well defined. Comparing cosmological expansion to local motions is a good approximation at small scales -- and this makes it hard to explain the difference between local motions and expanding spaces in terms of observation. A full explanation in terms of local motion does fail, as you say; and we do need to use expansion of space to fit the observations.
Cheers -- Sylas