I want to echo recommendations for
Four Swords Adventures (preferably with friends, but solo still ok) and
Jungle Beat (with the Bongo controller). Both are unique and really entertaining. And I'd argue that
Rogue Squadron 2 remains one of the best console-based Star Wars games available, although the controls will take some getting used to.
Some games that nobody (edit: except ShyGuy... oops!) has mentioned yet are the
X-Men Legends series. Both can be found cheap, and are fantastic games. Action based, with a reasonable amount of character customization/leveling up to enjoy. I definitely recommend that you check some reviews to see if they would be up your alley. There are also two
Baldur's Gate games on GameCube that offer a similar experience with more of an RPG-based setting - if you see either for a reasonable price, they are worth grabbing.
...
How are the rpgs on the GC, like Phantasy Star online 12&3 or Baten Kaitos, besides Tales of Symphonia I haven't really played any.
In my opinion, there are three must play RPGs and a few others that are still worth playing despite flaws.
Must play games:
Tales of Symphonia,
Paper Mario Thousand Year Door, and
Skies of Arcadia. All are great experiences and these games (in my mind) are clearly the best RPGs on the console.
Others:
Baten Kaitos has a pretty good story and a really neat battle mechanic using card combos. People gush over the graphics, but I don't feel they hold up that well today. Voice acting was pretty lame, and the overall pace and game design felt kind of plodding... but I happily played to completion once and would recommend it for fans of the genre.
Baten Kaitos Origins is supposed to improve on the first game, but I haven't played it yet. (However, I enjoyed the first game enough that I would feel comfortable recommending this to most people on reputation alone.)
Final Fantasy Crystal Chronicles is similar to Four Swords Adventures in that it's an action-RPG where you work together with several friends who have GBA systems connected to your console. If you have all of the required hardware and a few friends interested in playing together, then I would recommend trying this game - but that's a pretty high set of requirements for many people. Not as good as Four Swords, but still interesting and (mostly) enjoyable.
Fire Emblem: Path of Radiance is worthwhile for any strategy RPG fans. My personal favorite game from the series - although I haven't played Awakening yet. I always struggle to consider strategy games like this actual RPGs though, and don't really think it's good enough to justify current second-hand pricing trends. (Great game... just not $100+ great.)
Lost Kingdoms (and the sequel) are worth trying if you can find them cheap, but I wouldn't pay too much for either game personally. They also use a card-based system for combat, very different from what Baten Kaitos uses though.
I have no experience with Phantasy Star Online but have heard a lot of good word-of-mouth. Kind of wish I had given them a shot... but already have too many games on my backlog to look back now.