I'm going to go with Super Mario Bros over Mario Bros. Everything about the game was revamped, especially the controls. Rather than being restricted to one screen, the player could go for minutes in one direction. In addition, there were branching paths with warp zones leading not only forward, but also backward. Super Mario Bros introduced a variety of new characters and powerups as well as some of the best music in the business.
The jump from Metroid to Super Metroid also deserves a mention. No doubt, Super Metroid to Metroid Prime is also a gigantic leap, but for some reason it doesn't feel like the comparisson should be allowed. Metroid Prime may be a Metroid game, but I really don't feel like it is a continuation of the mise en scene of Super Metroid. I'm still hoping for that game one day, actually.
Going from the single screens, or multiple static screens, of the second generation to the multi-directional, per-pixel scrolling of the third generation is arguably as big of a deal as going from 2D to 3D, in terms of revolutionizing gameplay, and is definitely underhyped compared to the 2D to 3D jump.