Collection involving (possibly specific) trade is always fun, methinks. It makes it a bit more interesting. Like the longsword quest in Ocarina of Time, or some parts of Monkey Island.
I was fascinated recently to hear of a human-mouse (or some kind of rodent) food trading tradition in Siberia, in which humans would dig up the mice's tuber stores, but in exchange put some dried fish or something, something that the mice like but can't get themselves, so as not to starve out the mouse colony. It'd be interesting to have something like that -- animals, non-humans, or humans of other cultures, where you can't exactly communicate, but you can manage to get into mutually-beneficial exchanges.
Or just a bit of memory. Like having something clearly mark itself at some point in the game (if it's story-based or at least progressive rather than individual levels) and only later into the game introduce a collection quest where you need to remember about this and return in other to collect it (an idea that popped up for my puzzle platformer was to have a chandelier fall into the ground [already coded that part] and later have a character who wants something shiny at which point you will have to remember the chandelier and go back to pick up the crystals that fell off of it).
That'd definitely be neat, and it could combine with the pattern recognition. Like one thing you can learn is where a resource tends to be, but another thing you can learn is its relation to things in the past. Something where you say "Hey, I think this was in the spot where I did X fifty years ago. I wonder if I go to another place where I did X, there'd be another one..."
In general, the idea of this taking place across the ages is a good twist. If you collect every single X, kill every single Y, it might mean that X and Y aren't available in that area in the future. That's another skill,
inhibition -- can you refrain from a reward now for a future reward? (That might end up as frustrating, but it might end up giving the player an interesting strategic choice.)