Mmm.
I'm going to recommend a few gamecube games first, see how you like them. But there are some caveats to each of these, and they are pretty important.
Eternal Darkness: Sanity's Requiem - this one is the one I have the most hesitations about recommending. It is a psychological thriller with the spice of a horror game. It is very violent where appropriate, but not senselessly so: all of the violence is supposed to be frightening or disturbing, and it is never minimalized in any way. You do not commit violence against any opponents who are human: everything is some Lovecraftian horror basically out to drag you screaming into the shadows.
The plot of Eternal Darkness is very cerebral and fast-paced, each of the characters is very interesting and unique (you play as a dozen or so), and nothing about it feels cheap or as if any punches were ever pulled. This is my most recommended game on the entire Gamecube, but it is difficult to find nowadays (though inexpensive) and is probably the most legitimately adult game on the market. There's no sex or anything like that, but this is not a kid's game by any stretch of the imagination.
The difficulty is a bit steep in spots, but fair: if you panic, the combat system will leave you in the dust and then stab you. There are dozens of tiny details that people may not notice at first (like if you swing your sword in the wrong direction when you are by a wall, it will get stuck in said wall and not connect with your hated enemy). The magic system is intuitive, and the premise of the combat is about asserting your dominance over your perceptions.
I could ramble about how awesome this game is for a long time, and it is, but I have to stress that it very much may not be for you. It's scary, it's violent, it likes to play tricks on people...
But Miyamoto did produce, and his touch is apparent in certain areas.
F-Zero GX - this is, without doubt, the most awesomest, bone-crushingest, slap-banging rip-roaring best racer ever made ever and I will fight anyone who says otherwise. The level design is absolutely insane, the sense of speed is unparalleled in any other game, its multiplayer is a blast, and the game looks absolutely gorgeous either on a standard TV or running in 480p.
Since you like F-Zero Advance, I am almost positive you will like this, but there is one caveat:
If you buy this, it will be the hardest game you have ever played, bar none. Now, I'm not saying that the Grand Prix mode itself is hard - it is, though - I am saying that the Mission Mode or Story Mode or whatever is so bone-crushing that there are some who claim it is outright unfair and even some who acknowledge its balance never manage to finish it. This is not so bad: for the experience, it's worth it.
But completing the Mission Mode is necessary for unlocking some of the levels.
I recommend this game wholeheartedly, no hesitation. But if it is too hard (and it may be) download a save off of the internet and stick it on your Gamecube memory card. You will save yourself a lot of heartache and heartburn.
Fire Emblem: Path of Radiance - this is a very good game and not a terrible intro to the Fire Emblem series, but if you want the best of the best in terms of intros you might honestly be better off picking Fire Emblem on the GBA, which is the best possible introduction you're going to get. Hector 4 life!
I am not as enthusiastic about this one as the rest, but Fire Emblem as a rule is rock hard but completely fair.
Harvest Moon: Magical Melody - All right, this game is an acquired taste pretty much like no other. I am not even kidding. It is, however, arguably the ultimate entry in my second favorite game series.
Harvest Moon's concept in every game is simple: you inherit your father or grandfather's farm and you are supposed to take care of it. That's it. No monster battle, no fancy item collecting, none of that stuff. You clear your property, you tend the land, you water your crops, you pick them so that they can be sold at the market. It's a very simple, almost relaxed game that is nonviolent, upbeat, and pure fun.
I say it is "almost" relaxed because it is also unlike pretty much any other game out there in that there is a definite time limit on everything you do. Days are only about ten to fifteen minutes long (though time stops when you are inside a building, if I remember) and your crops will wither and die if you go too long without watering them. Add in animals to take care of, townspeople to befriend, the possibility of trying to marry a girl (or boy, if you play as a girl), the ability to buy and build extensions to your house, and the ability to buy more land, and you suddenly have a game that can be so very busy that it is why I am so easily bored by Animal Crossing. This game waits for no man, and though its rewards are sweet and its tone is gentle it is not going to pull any punches about the mistakes you make.
The simplicity of the game, though, the earnest fun of it and its quiet dignity and its simple humor, are what make it endlessly charming. Any game in this series is good - if not this one, grab Harvest Moon 64 because it is wonderful - but this one is probably the best. I recommend this without hesitation. It may take you a while to get into, but there is nothing not to love about this game. Period.
Pikmin - if you're picking up the Play on Wii version, cool. If not, grab the Gamecube version! Others have explained why this game is so awesome so I will leave it to what they said. It is pretty awesome.
Pikmin 2 - Also awesome.
Prince of Persia: The Sands of Time - All right now we are getting into the really good stuff. Generally underappreciated and completely masterful, this game may be a bit tough to find but if it interests you even a little bit, I am begging you, look into it.
Prince of Persia's primary strength comes in its fluid, intuitive platforming, where every environment becomes a puzzle and the solution lies primarily in one's ability to traverse the area without falling into the abyss or onto a bed of spikes. In terms of platforming, this game is pretty much unmatched, and there are few games more satisfying to beat just for how radical the platforming can be.
The combat is a bit repetitive but it is not needlessly violent: everything you fight is a monster made of sand which can be absorbed into your dagger, which can be used to control time in various ways (as you may have heard). The ability to manipulate time is very important - particularly the (awesome) ability to rewind time. As the platforming is often very difficult and it is sometimes easy to make a mistake in combat, the ability to rewind time for about ten seconds at a time can mean the difference between simply trying that same jumpm again and having to redo a whole area. It really cuts down on the frustration factor!
One of the primary reasons I recommend this game, though, is for the writing and the acting. The voices are a bit tinny-sounding in the Gamecube version, but the actors themselves do excellent jobs of bringing to life chaacters abotu whom it is easy to care and defend. Everyone has motives that are easy to believe, they grow in ways that one might not expect in a game of this type, and yes, it pulls off what is arguably one of the best romance-ish plots in recent gaming memory.
If you enjoy this game (I hope you do, I am almost sure you will) then consider looking into Prince of Persia: The Two Thrones, which was also released on Wii as Prince of Persia: Rival Swords or somesuch. It's actually the third game in this particular story, but the second game, Warrior Within, is not worth your time and is more or less intellectually bankrupt along the lines that you prefer.
Sonic Adventure 2: Battle - GASP, I hear you say, A Sonic game! How impudent, to suggest sullying my home with the long-dead rival of the company I love so much.
Now hold your horses, hold your horses, this game ain't bad at all, and it's definitely better than the alternative Gamecube title, Sonic Adventure DX. There are three kinds of gameplay in this game:
Knuckles/Rouge levels, which ae basically treasure hunting levels using a hot/cold system for finding treasure. This sounds simple, but the levels are huge and the treasure is often hidden in very odd places (facilitated by the characters in question being able to climb all over the place and burrow into surfaces). This is a pretty fun level type!
Tails/Eggman levels, which are pretty straightforward shooter levels. You're placed in a mech which has the ability to shoot down many of your robotic targets as you walk along. You shoot enemies, you dodge out of the way, that's pretty much it. Good mindless fun.
Sonic/Shadow levels, which are the entire reason to own this game. Theese are pure high-speed platforming at its best, and the whole reason they had to break this game up into different types is because each of the Sonic and Shadow levels are so huge and complex. These level types are endlessly replayable and very fluid, and I would recommend these games for them alone. The sense of speed you'll get in some parts is ridiculous (though still not F-Zero GX ridiculous), and if you haven't played a Sonic game and don't want to spring for one of the new releases, this is one to look into.
Star Wars Rogue Leader: Rogue Squadron II - You probably already know about this game, since it was a launch game for the Cube and you pobably had to choose between this and Luigi's Mansion (not a hard choice for you or me, but we went in opposite directions). There is a Penny Arcade strip that does a pretty good job of explaining how this is basically the best arcade-style space shooter ever, but really, you have to try this for yourself.
It's hard as nails in some missions, and if you don't like Star Wars that's going to be a tough hurdle to jump over, but this is honestly one of the most fun and rewarding games on the Gamecube, as well as still being the most beautiful title on the platform in many respects (it looks better than many first-year Wii games).
There are something like a dozen different ship types to fly and fifteen different missions you can partake in, each of them with a very real story relevance and tending to be set in or between the movies.
You may have heard of this game's sequel, Rebel Strike, including pooey on-foot missions that broke up the gameplay and basically shot it in the foot. None of that here! This game is pure unabashed S-foil-locking awesomeness.
Really I don't see how I can recommend this one in a way that it doesn't already recommend itself. It's the ultimate Star Wars flying game that isn't on the PC. And it's fun. And pretty.
Viewtiful Joe - I'm not going to be able to do justice to this one, so I'll just give you a premise and a video.
You are Joe, a movie buff who loves superheroes. He is, through a wacky twist of fate, sucked into the movies, where he has to save "Movie Land" using his crazy Viewtiful Joe transformation and its powers, including Slow Mo, Zoom In, and Speed Up, all of which sound very silly but all of which are very fun.
The game is hard.
But the game is awesome.
Really awesome.
