Well, the first quest is designed to prove your worth--it should stay where it is. The thing that needs fixing is this minimum rarity limit (i.e. it has to be as rare as x or rarer). That's utterly absurd. I mean, c'mon, it's Thrundarr's first quest for goodness' sake! You can get it at level 6 if you really want! In addition, it doesn't make any sense to have it be so rare because then people can rarely take the second quest because you have to explore beyond the AF before then [unless you are getting super grindy, which it would be bad of the game to encourage], and you only have 50/50 chance of not entering AF and screwing the quest in the first place, not to mention sometimes DH is untraversable.
Anyway, I guess choice one; I mean, really, why not just choose a monster of x DL (i.e. all monsters up to x DL) at the rate they are spawned? That would offer plenty of variety and not screw people most of the time. Maybe that was previous behavior, but the previous behavior was a lot better than this. If not that, I guess a max rarity limit, but that makes the quest more of a formality than anything.