Rogue (1980) is the progenitor of a PCG genre known as "Rogue-like". A player (denoted typically with an '@' character) traverses the floors of a procedurally generated 2D map, navigating obstacles, traps and enemies to get to the bottom. The player has a limited amount of food that may be replenished by looting, but each move in this turn-based tile game costs food; to venture further into the floors is to risk starvation and the brutal perma-death mechanic of this game.
Rogue, and its spin-off Nethack, was my first experience with games that run in the command line. I can only imagine the complexity that co-creators Michael Toy and Glenn Wichman faced as they developed this game for Unix, using a very nascent graphics library known as curses (developed by Ken Arnold. They also were restricted to only using ASCII character to represent their procedurally generated world. Rogue ended up being included in a popular distribution to the internet's predecessor, ARPANET.
"Rogue is the biggest waste of CPU cycles in history." --Denis Ritchie
The map generation algorithm used in Rogue, and consequently many titles in the "rogue-like" genre, follows the following instructions
1) Divide the map into 3x2 cells
2) Choose to/not to draw a room within each cell
3) Use a "drunken walk" to connect the rooms
Prior to Rogue, most adventure games lacked replay value and complexity. Toy and Wichman realized this, and came up with two clever ways to deal with effective complexity, the first of course being the procedural map generation and mob placement algorithm. The other one being "perma-death" was a controversial topic during development. I would argue the "perma-death" mechanic aids the effective complexity of Rogue since the player is unlikely to come across similar levels given the persistent consequences of death.
Here's a video of one of my favorite Youtubers, Scott Manley, playing the original Rogue game.