One of my favorite easter eggs is for a mod of Half-Life 2 called Black Mesa. Followed the mod for 7 years (still following for part 2), but one of the most elusive easter eggs is called the Pizza Code Mystery
Basically, the developers put a very complicated (and unsolved) bunch of tidbits of information all over the game using mathematical equations and codes (which a lot of people in here seem like Einstein's due to all the equations and math thrown around that I am clueless about) which tells a story about some scientists. It is goofy and silly, but so many people spent HOURS and HOURS looking through the game in order to solve this. Some of the clues you had to cheat (disable clipping) in order to reach areas of the game where the codes were hidden. Obviously, this was something done after playing through the game. I'm not saying this is something along the lines of 'lore' BUT it makes you think many long hours about these things.
Now, picture randomly, throughout the procedurally generated universe, you find a derelict ship, or maybe MANY derelict ships in a system. When you get near, you get bits and pieces of information about an ancient race of spacefaring people who are no longer around. Now, it is probably too much effort to come up with a story or something to just make you think "What the heck happened here!? Who were they fighting? Who won? Did they survive?"
The only other way to make this even creepier or eerie, would be if you could board a derelict ship and go inside, and find the ruins and bodies(or lack thereof) in the ship. Some games did this stuff and it sometimes led up to meeting of an unexpected enemy or just set the tone. I always HATED having to do that mission where "We need you to go on board that super dark and creepy looking ship to find out what happened there. What could possibly go wrong?" Now, I know this might not be the best game to use as an example, but there was one level(or a couple) in Star Trek: Elite Force where you find a derelict ship and it is completely empty until you find the ship logs with people screaming that they are being torn apart.
Those moments gave me goosebumps and made me increasingly paranoid.
Ok, rambling done (I think I jumped around more than a frog on cocaine) but I am just spitting out ideas because I like having some unexpected things thrown in here and there randomly. The spice of life. Heck, Josh could even ask for someone to come up with a handful of different ideas to make it easier for him. We do have a bunch of super geniuses on here.
"Everyone needs to have their avatar's edited to have afros." -Charley Deallus