Do all Legacy decks need to be combo-heavy in order to win? What's a good indicator that a deck will hold up well at a tournament?
not really
No, but you need to do something to interact.
If your deck sucks against combo, then you need to play basically 12-15 anti combo cards in your sideboard.
I came 3rd with this pile the other night: take note on how many anti-combo cards I have, tailored for my meta:
4 Cursed Scroll
4 Figure of Destiny
4 Grim Lavamancer
4 Mogg Fanatic
4 Rakdos Cackler
1 Sulfuric Vortex
2 Eidolon of the Great Revel
3 Fireblast
4 Lightning Bolt
4 Chain Lightning
3 Rift Bolt
4 Bloodstained Mire
7 Mountain
4 Rishadan Port
4 Wasteland
4 Wooded Foothills
SB: 3 Ensnaring Bridge
SB: 4 Leyline of the Void
SB: 3 Mindbreak Trap
SB: 2 Pyrostatic Pillar
SB: 3 Smash to Smithereens
Beat Miracles and ANT, lost to Elves (but he had it all so whatever)
Using a combo is just one route to victory, while legacy definitely has better combo cards than the less powerful formats it also has a wider variety of aggro and control cards.
Are you new to eternal formats?
No, you don't need to combo. Look at agro decks like Fish and Burn. Combo is just one option. >>46264227 is right in that you do need to be able to interact with combo at the very least. Fish has counters like Force and Chalice, and burn... Well burn doesn't give a shit.