3D World certainly has it. 64 and Odyssey as well albeit in a not entirely comparable nonlinear way.
SMW has quite strong storytelling in a sense too, but the focus there is on the meta story of the world map rather than the relatively slack levels themselves.