I know I wont make a lot of friends by saying that... but having to explore a map with a line of sight/fog of war would be nice. A solo optimization could fit with that. Walking through a dungeon having to find treasures/loot or fighting enemies, checking around the corner, or maybe even have to avoid enemies, by guessing where they will go and take a path around.
Mixing a labyrinth with line of sight/fog of war and guessing enemies movement to avoid them or get them from behind and kill them. Or even have a concept of orientation, to where you are looking at so you see in one direction, while something could be comming from behind