The Wager (2011)
Remember of Seven Cities of Gold? The Wager is also a game about exploring a procedurally generated unknown. Though instead of SCoG’s disembarked expeditions, the islands in The Wager are little story snippets or choices, a bit closer to Strange Adventures in Infinite Space. The stories also procedurally distributed, so even if you know that having the parrot will solve this particular encounter, there’s no guarantee that you’ll have previously discovered a parrot this game.
Originally created in the Ludum Dare game jam by Surprised Man (a team of Peter Silk and Kieran Walsh) The Wager has since been expanded with a bit more polish and a few more features.