Half-Life 1 did this so well. It was primarily a shooter, but if you followed closely you could get a story arch. You never lost control of you character and every cutscene was optionable( except the very first and last, you still need some pacing ). This is why I consider Half-Life 2 an inferior game, even though it does everything else better, you constantly get into situations where the main characters talk for several minutes and you can only watch and wait. HL1's gameplay flows, HL2 is a stop-and-go.
I agree, except that even on modern machines HL stops the game every 2 minutes to load the next area (this is especially painful when the train is moving through the intro cutscene.)
