I think you definitely should avoid picking at random in order to make sure that each round of selections is a tougher choice than the last. You could do something like seeding in the NCAA tournament, and base it either off aggregate critical reviews, sales, opinions of others, or your own judgment of what the most generally popular games are. One thing you could look at is the favorite Zelda poll at the top of this subforum. Each of these options have flaws like critical reviews being harder to find for the older games and the favorite Zelda poll just recently added Skyward Sword.
Personally I'd just pick it myself and my suggestion would be:
Number one seeds: OOT, TP, SS, WW
Number two seeds: ALTTP, MM, LA, LOZ
Number three seeds: MC, OOA, OOS, ST
Number four seeds: AOL, PH, FSA, FS
And then I'd suggest ranking within each seeding so that the top #1 seed plays the bottom #4 seed (i.e. OOT vs. FS in my example), but also so that the top #2 seed is paired in the same bracket as the bottom #1 seed (i.e. ALTTP vs. WW in my example).
Basically it would look like this:
1 v. 16 (OOT v. FS) 2 v. 15 (TP v. FSA)
8 v. 9 (LOZ v. MC) 7 v. 10 (LA v. OOA)
4 v. 13 (WW v. AOL) 3 v. 14 (SS v. PH)
5 v. 12 (ALTTP v. ST) 6 v. 11 (MM v. OOS)
The winner of 1 v. 16 would play the winner of 8 v. 9 and similarly for the other quadrants. The quadrants with 1 and 4 would meet in the semifinals as would 2 and 3's quadrant semifinalists. I'm pretty sure that's the most fair seeding arrangement possible- I don't think I messed it up .
Of course those are just my suggestions, but I think you should use the same format of seeding with the bracket. Also once you do it all, you may want to shuffle some games slightly to avoid horrible draws for one of the higher ranked teams. For instance in my example Skyward Sword is absolutely screwed by being put in the same quadrant as Majora's Mask so I might consider swapping ALTTP and MM. Good luck with setting all this up.