Para mi un fps literalmente es eso solo disparar y matar, sin embargo el fps con trama implica que aparte de disparar y matar/destruir, se necesita interactuar con partes y/o personajes del juego para poder conseguir completar un nivel o estado.
Los ejemplos que menciona julian sobre quake 1 y 2, son validos en la medida en que al inicio del juego se menciona la historia de los logros que hay que conseguir para completarlo y en algunos apartes del juego hay cierto grado de interaccion (como por ejemplo switches de areas secretas o puertas, etc), sin embargo el objetivo del juego no cambia, dispara y mate a todo lo que se mueva.
En el caso concreto de half life o tomb raider (este es 3rd person, pero igual quake 3 se puede jugar 3rd person), por ejemplo, es necesario interactuar con los personajes del juego para poder alcanzar los objetivos, es asi como por ejemplo se requiere de claves, llaves, dialogos y tiempos determinados para poder resolver ciertas situaciones, de ahi la diferencia entre el FPS LITERAL Y EL FPS CON TRAMA / HISTORIA.
Otro ejemplo de trama/historia es MAX PAYNE, en el cual, si bien la interaccion con personajes se da de manera corta, esta interaccion es requerida para resolver ciertas partes del juego, al igual que dentro de la totalidad del juego, hay referencias concretas frente al porque del juego en si (una organizacion que implica ramas de poder, vinculos con la mafia, etc), de este tipo de FPS es que trata el foro.