It may be too late in the development cycle for this, but I thought I'd put it out there.
Background:
Shrines are (currently) boring to me. I've kind of realized why now. The problem is that I can donate anything at any time and so when I want favor I just kind of aimlessly acquire things of relatively high value and donate them until I have enough favor to get an emblem or learn faster etc.
Contrast this with street projects where you need specific items to advance. Here you have a goal: Make 20 Cold Tacos. And since my action feels more directed, it is more interesting.
Proposal:
In place of (or in addition to) donating specific goods to shrines, have each shrine make the player a random offer. Bring me X specific goods and I'll give you Y favor.
Details:
The favor given would of course be based on the existing favor given for those goods. The goods can be specifically selected based on what the player can make. The randomization method can be weighted towards asking for higher-favor items.
One nice thing is that you could have the seed be based on a hash of a counter (number of fulfilled requests to this giant), the location, and the player name. This would mean that a player would see different requests at different shrines for the same giant. And when they fulfilled one request, all the shrine requests for that giant would be re-randomized.
Learning new skills would not change the existing offers, but would cause the new items they can make to potentially appear when the offers were reset.
This would only require a constant amount of storage per player: one counter per giant and a bitset per giant showing what skills were available to that player when the last request was made.
Additional Note:
A similar system could be added to street spirits which would make them pay bonus currants if you bring them X specific goods. This might make earning money more interesting and goal-directed as well.