I like a story that is basically realistic, something that you see have probably happened sometime in our history too (empire conflicts, beytrayal of kings and leaders etc).

As for gameplay, I am very fond of being able to choose race, class, alignments etc for myself. The more I can choose from, the better. (Oblivion, Morrowind and Baldur's Gate I and II are good examples of what I mean).