My first combo was Pestilence (yep, even then) and Giant Shark! Here's how it works, in case you don't remember Giant Shark.
Step 1: attack w/ GS (4/4; +2/+0 and Trample if Giant Shark is blocked by a creature that has been damaged this turn).
Step 2: do 1 point of Pestilence.
End result: Block, and the Shark gains +2 and Trample, and does a major beatdown on any wimps that block it. Don't block, and take 4 from the mighty Shark!
Fun, fun, fun!