Deus Ex: Human Revolution gives you three options for starting a new game, "Tell Me a Story", "Give Me a Challenge", and "Give Me Deus Ex":
The wording seems to imply that there's more difference than just tougher enemies (i.e. more/less emphasis on story), is there?