Get Killer7 even if you get something else, too. I think it's down to like $7 used now.

Otherwise, I've heard BKO was like the first game, except with non-annoying voice acting, so I say go for it! The first Baten Kaitos was fun stuff, and pretty to boot.

Okami!

Since all the rpgs have been suggested, I'll suggest shooters, Time Splitters 2 and Future Perfect for the gamecube.

edit: I see you posted you hate shooters, well than i suggest fire emblem BUT those shooters are great and you should check them out if you haven't already.

The campaign is still continuing, BUY ZACK & WIKI!!!

Super Paper Mario?

Well I bought a copy for my friend for 29.99 canadian from a small game shop a year ago, so I can't imagine the price being too high.  

Eternal Darkness!

Oh wait, Im too late :(

DK Jungle Beat deffinately, otherwise try Eternal Darkness if you havent got it already

Love RPG's, here a suggestion, buy an old GBA and final fantasy IV,V,VI, it wont cost that much I think

Pikmin 1&2
Viewtiful Joe 1&2