The biggest advantage of winning the first quest is second quest choice. A lot of people just see the quest rewards and say "Eh, it doesn't really matter, so the heroes should just go for the search tokens." They incorrectly assume that all quests are created equal.
You make some good points, but I still think adding a reward is the way to go if I'm going to use the house rule I've come up with for two reasons. First, I generally play with mostly newer players, and the advantage of picking the second quest is definitely reduced if you lack experience with the game. Second, although picking the second quest is good, I would argue that it's not as good as getting 4 threat/fortune.