Kabhold-
I would definitely recommend Paper Mario: The Thousand Year Door. It's a completely awesome game. I'f you've played Paper Mario for the N64, I think you'll agree.
I'd also recommend Tales of Symphonia. It's one of the best games for the little cube. And then you can get Tales of Symphonia: Dawn of the New World for the Wii also!. =]