The first game I remember having morality choices be a central part of the gameplay experience was Knights of the Old Republic, which I played circa 2004. Prior to that, every game seemingly had a fairly linear structure with one defined outcome. You had no say in how your avatar acted or reacted; it was basically a movie with gameplay interspersed.