Refresh rate is the rate at which a screen refreshes. Every second, the screen refreshes several times in response to animation. Mario moving one block right happens during many refreshes. Even though he might have used 4-5 animation frames, the screen updated many more times. Even when you are standing still and NOTHING is happening on the screen, it is still being updated/refreshed/redrawn several times.
Poor refresh rate causes what is known as "ghosting," in which there is a small delay in a screen update, causing things to blur/ghost images to appear. If you had Mario walking across a completely white screen and the refresh rate isn't up to par, you'd see a ghosting afterimage effect. So when Mario moves one block over, you might see some fuzziness resulting from the previous refresh not happening quickly enough.
If you've played a few Castlevania games (Symphony of the Night, Aria of Sorrow, Dawn of Sorrow, and Harmony of Dissonance all do this) , you'll notice the main character ofter has a trail of himself behind him. While in those games it is a graphic effect, ghosting would be that effect but multipled and spread across the entire screen. So instead of just the character having an image trail, the background objects do as well. In a Mario game, every block, coin, Goomba, and Koopa would all do this as you moved to the right/left/up/down. Ultimately it becomes horribly disorienting and can cause eye strain/stress/nausea, although usually it is just very, very annoying.
It has nothing to do with slowdown, which is a breakdown of the system's processor unable to handle too much on the screen, which can result in everything moving slowly. This usually only occurs when you have a ton of sprites on screen and/or some sort of additional graphic effect is going on (Mode 7, for example).
Offtopic: Square can eat **** for causing FFIV to have tons of slowdown.