FPS games hardly have any storylines as they're geared towards multiplayer which has absolutely no storyline.
Mass Effect 2, Dragon Age Origins, Bioshock, Deadspace, Fable II, Fallout III, Too Human. Those are games I still enjoy playing that contain storyline and decent graphics. Getting them for PC ensures awesome graphics though considering your PC can handle them.