Hoo boy. The Gamecube years were my favorite as far as console gaming goes. Here's a partial list of recommendations:
Fire Emblem: Path of Radiance: An enjoyable turn-based strategy game based around careful unit placement and keeping track of all of the variables. And shipping. Your units are all unique, irreplaceable characters (that you can develop relationships between, increasing their abilities) and if their HP goes to 0, they're gone. Forever. Story is fairly enjoyable as well.
F-Zero GX: AKA "Nintendo please make another one why won't you make another better F-Zero what is your problem". Racing along looping, twisting tracks in an anti-gravity vehicle alongside 29 other competitors at ludicrous speeds. Ridiculously fun, ridiculously fast-paced, and the AI actually plays fair. There's a story mode (nothing special, tbh, but allows you to unlock new vehicles) as well as the grand prix tournament style mode, and multiplayer. You can even design your own vehicles, though the system is somewhat limited.
Metroid Prime: Metroidvania platforming and puzzle solving combined with first-person shooting - not CoD-style cover-shooting either, but based more around using your superior agility to move around enemy attacks. Works surprisingly well, but if you own a Wii you might just want to get the remake. Some really, really nice environmental effects, like raindrops gathering on your visor if you look upwards.
Tales of Symphonia: Probably the best-known JRPG on this console. Epic length, fun battle system, plenty of depth and replayability. Plenty of side things to do alongside the main quest as well.
Skies of Arcadia: Legends: Narrowly beats out ToS as my favorite RPG on the Gamecube. Not quite as long (but still lengthy!), makes up for it by having a far more interesting world, more likable characters, insane super moves, and a unique battle system for ship-to-ship battles. Graphics are nothing to write home about, but perfectly workable. The Legends remake also includes a wide number of extra things to do that never made it into the original Dreamcast game.
Resident Evil 4: Sure, the plot is crazy as all get-out. But as the first RE to include actual intelligent enemies (for a certain definition of intelligent...), it made for a refreshing change from fighting zombies. Keep in mind though, that it's not really a horror game anymore. Just try to tell yourself that when a madman wielding a chainsaw is chasing you...
Eternal Darkness: Sanity's Requiem: Oh god, this game. Where RE4 sacrificed horror in favor of action, this game went in almost the exact opposite direction. The enemies and characters are unsettling, the plot twists and turns and is frequently depressing, and you are almost guaranteed to be freaked out at least once, often when you least expect it. Best played in the dark, both in terms of your playing space and in regards to spoiling yourself.
Paper Mario: The Thousand Year Door: Fun and quirky, as might be expected from a Mario game where everyone is literally two-dimensional. The various partner abilities and the transformations you gain access to are used to great effect when puzzle solving and exploring, and the writing is frequently hilarious.
Time Splitters: Future Perfect: Not the best FPS out there, admittedly. However, I loved the sheer silliness of the characters and plot, it has some really nice moments where you cooperate with your past and future selves, and the multiplayer is a blast. It also has one of the best level editors I've seen on a console game (until Halo and whatever came around) that even allows you to make custom stories, if you're so inclined.