The Lost Levels for the win. There is no better satisfaction then of finally betting of those ridiculous levels and being able to claim that you have done so. The game is Mario on crack and I loved how it would fuck with you at every turn. Poison mushrooms, warp zones that go backwards, hidden blocks that require the most painstaking accuracy to hit and so on. The lost levels is by far one of my favorite games.
Mario 2 (us) is also a great game in its own right, but its got nothing on the lost levels.