I'd say the Gamecube's two best: Soul Calibur 2 and Melee.
Soul Calibur 2 offers a great selection of characters that all have evenly balanced downsides and good sides (except Charade and Cassandra who I find are horrible fighters both when I play as them and against them) and whenever I introduce my friends, they instantaneously get the gist of how to play. Heck, I remember having a friend over, who after just being introduced to the game, beat my record in Survival mode. I find my best characters are Link, Cervantes, Necrid, Nightmare, Voldo, and Astaroth. However I do occasionally play as Kilik in a mission.
Melee is just awesome. Great controls (as opposed to Brawl's feather-weight controls) great graphics (the smoothness and purity in the textures are all great, and they remind me of a couple games on the glorious Dreamcast) great gameplay (I've been playing the game for over a decade, and I have yet to be sick of it) great music (the Fire Emblem track did a good job of turning a dire conversation theme into a raucuous battle theme) and great character selection (I don't suck with anyone in Melee.) Also, the multiplayer is sublime. Whenever I have friends over, they start out whining for Brawl, but by the end of it, they usually walk away saying they had more fun in Melee.