I quite like the option X talked about in the long post, of three choices and a reroll button. I don't think i'd be pushing that button, but it would feel to me like an unobtrusive way of giving people more flexibility.
Another idea, tho, out of left field: perhaps upgrades would feel more interesting if they were harder to acquire. As it is they're kind of trivial, even if potentially time-consuming. Maybe it would be worth changing to a system where the first three to five were just free, but then adding more was hard enough to be a real strategic choice. Actually, upgrades seem like a perfect opportunity to develop the theme X talked about earlier of developing the individual vs. the community. So two suggestions:
One, make upgrades past the base level available only as a mission reward. Just based on the name I'm tempted to suggest it would be "Journey to Perfection," but I think that would get me lynched if it. were implemented. This option would still make all levels of upgrade available without giving anything up (now that CP is gone), and it would make heavily upgraded characters much more valuable. It would also resolve the inflation problem of some players having essentially unlimited upgrade stones.
Two, would be to bank heavily on the individual/choice dynamic. Create two special missions once per tier, one of which would open a new upgrade tier (I suppose starting with six, the first five being free) permanently for all characters on the continent, and the other would provide some benefit to the community. The obvious choice there would be opening up a new tier of settlement buildings, but for that to work guardian powers would have to be heavily reworked. Seek survivors would clearly have to be a level one or two power, and the high-level powers would have to be made much more attractive. But especially given the diminishing returns of upgrades, I could see it making sense to give up a few levels in favor of other powers like serious continent-wide buffs and more specialized seek powers. This would of course create a coordination problem in multiplayer which might be insurmountable.
EDIT: Of course, in the second system finishing one special mission would make the other disappear.