somedude: The game I can remember that most interested me in this sense was the Marathon series, especially the interplay between the AI systems.
Very true. The Marathon series of games has possibly the deepest and most enthralling universe of any I've ever played. That includes Fallout, Myth, and Half-Life. Marathon's story is right up there with all of them. Being a Mac game originally, it flew under the radar of most PC gamers myself included. You can actually download all three games in the Marathon series for free and play them on PC, Mac, or Linux these days. Just check out
source.bungie.org/get. It is completely free and completely legal, as Bungie released the games as free ware a couple of years ago. The game is certainly worth playing, especially for those of us who are not deterred by the graphics in early to mid 90s FPS games.
Myth: The Fallen Lords also had a great universe. It was loosely based on a series of books by Glen Cook called "The Black Company". Myth was so good, I went out and read all 10 books in the Black Company series.