That's a classic, and it can be pulled with success on the party at any level. For example, our party had been hearing about this other paragon-level adventuring party since Level 1, and finally got to a point (around Level 6 or so) where war was breaking out. We wind up working for the same side as this other legendary adventuring company. Of course, they get the tough main mission, without which the war will be lost, while we draw an easy side mission which doesn't feel anywhere near as important.#2) Players start in a tavern. An old man comes looking for adventurers to help him out. He picks his group and heads off to adventure. The PCs were the ones who were passed up, not the ones who were picked! However, they later get a hint that the other group is heading into a trap, so they've got a chance to redeem their smarting pride by proving themselves more heroic than the "heroes" who got picked first.
We fail at our mission, but they fail at theirs and (seemingly) suffer a TPK; the war is going very poorly. Rather than slink back to our liege with our tails between our legs, we head off to finish their mission for them and redeem our pride .. on pins and needles because whatever killed them off has to be much higher level than we are! It made for a great Level 6->10 arc!