I’d second the Mass Effect series for an excellent, well-told video game story (with pretty fun FPS-RPG gameplay, too).
Vampire the Masquerade: Bloodlines is probably one of the best action-RPGs I’ve played (and best games period). Fantastic setting with a lot of depth, darkness, and humor, great varied gameplay (you can create very different types of characters), and one of the best videogame stories ever.