Super Mario 64 was an N64 launch title. Resident Evil 4 was a late Gamecube title. In my mind that's probably the biggest gap in graphical fidelity between generations of console. But I can see how going from NES games like Super Mario Bros to SNES games like Star Fox would be a close contender.
PS1 -> PS2 -> PS3 or Xbox -> 360 feel more iterative because they started after the 3D era had already begun. We haven't had a new dominant paradigm for gaming since then (besides mobile gaming).
Elite did 3D on the NES so not as much of a leap.
I'd make that (non-Super) Mario Bros. -> SM RPG with the SA-1 Chip
I've heard that last part put as "we're further from the PS2 than the PS2 was from the Atari 2600." The statement really stuck with me.