So I'm gonna share some thoughts related to the genre I'm tackling into (procedural RPGs / roguelikes).

I think that "what is a main quest" should depend on what the player considers to be relevant: if he just wants to rescue his sister or slay the evil lich threatening mankind (who might or not be the one who kidnapped her in the first place, depending on the random generator) or take his place, that's up to him.

When he thinks he's done with that game, he should take some kind of conclusive action ("close the Chaos Gate AND leave the  Drakalor Chain", like in ADOM) or raise an army of undead that take over the world or reach the nirvana.

My examples are pretty D&Dish, and I'm focusing more on what could be used to feed the generator, as you guys have already provided a nice list of story/quest/event types.

---

1 - The setting

1.1 - Procedural world with random stuff provides general quests:

1.1.a: is there a settlement near a forest?

 - chance of wolfs attacking children: "the damn wolfs are taking our children to the woods and devouring them!" <<deal with hostile person/group/beast>>

1.2 - Character background:

(Something like ADOM or Dwarf Fortress or any roguelike with procedural character background generator...)

1.2.a: if you're an orc with somehow good alignment, blame humans (or elves) for something:

1.2.a.1: slavers raided your village when you were young

1.2.a.2 (clue) a randomly placed clue tells you that a randomly chosen human settlement is to blame for that; if you don't explore enough the world you might never find this (possibility of branching into multiple indirect clues that can take the player here, if desired, would be a waste not to avenge the family lol)

1.2.a.2 (possible quests trigger): <<deal with hostile person/group/beast>> (kill, imprison, enslave)

1.2.b if you're an orc with somehow evil alignment: pursue that one single children that escaped when you raided some village.

1.2.c: if you're an elf, with somehow chaotic alignment: when you were younger you fell in love with (some gender?)(some race?). At the time, the elders forbade you from following your heart.

1.2.c.1 (clue) a randomly placed common friend is found, which spent some time with both you and your loved one ages ago. He/she tells you that he heard from your love whereabouts. He/she points you to the direction of "your love". 

1.2.c.2 (possible quests trigger): <<find a person>> (went to the astral plane; got kidnapped; got killed; that's a  doppelganger!)

---

Alignment could restrict quest options, or instead your choices could shape current alignment - which could open certain types of quest and not others (mix restrictive paths x dynamic alignment depending on the quest type / relevance). Alignments could actually be just a label that results from what you've done so far in your life (some Q&A like ADOM character generator (questions mode), but that actually shapes the personality and not the skills):

"In your childhood slaves were forced to work in your neighborhood. Many of the slaves were too young, too old or too weak to work effectively. The forcemasters mistreated them and abused them all the time. Will you..."

Nothing really new here.

The real challenge is to implement it in a way that feels "natural"/fluid, right?

Very nice. Couldn't find the grass tile however (except for the jpg preview)...

@Zabin I'm feeling right now the pain of not being able to color blood or grass that looks like blood/grass. That's too bad, because by adopting a specific/broader palette we do distance ourselves from what could be a "more standard" standard (or at least one that is already used somewhere else)...

I might as well expand my palette - the final product is more important than the palette itself, after all. But first I'm gonna burn my head a little bit and hack those damm pixels.

Nice work you're doing btw. I'm hoping we can help each other somehow, even if we due seek different styles.

Ow yeah, David Gervais definitely has some great stuff.
I was actually checking his isometric surface map tiles today (Stone Soup doesn't really have any of that). Thinking about making orthogonal version of those dunes/hills (only the colors were automatically converted so far):

Any specific tileset or area you like from David Gervais?
Also, could you be more specific on the palette thing? I'm really just taking one that seems pretty popular around the web (even called a "pixel art classic" on some forums / tutorials). And for my untrained eyes all of his stuff seems incredible.