Sweet, someone's making SuperTux 3D...
Secret Maryo Chronicles is the slickest of all games for Linux graphically, for a jump and run side scroller anyway.
I'm still holding out for Super Tux 2, I like the protagonist a bit more.
A short list of my other favorite games available for Linux:
There are not many options in Linux for a native pinball game and this ones' development ended in 2002. It's not great to look at but the game play is good. I've been modding this game in my small amounts of spare time to give it a bit of a makeover a'la Neverball/Neverputt style. I'm working on a page to document what I've learned for anyone wishing to mod also.
This game comes as a bundled pair and is kind of a curiosity that it's not well known and is hardly mentioned in Linux game sites that I've googled. It's a pretty well polished. The goal of Neverball is to tilt the table around with your mouse to guide the ball around the course to collect as much coins as you can and reach the goal point before the timer runs out and progress to the next level.
Neverball is the more polished of the two graphically but I love mini golf so Neverputt gets more use from me. Both games have lots of levels and you can download more.
I guess I'll start this section off with a disclaimer: I'm not really big into computer games. The Xbox and Playstation don't interest me at all. Ironically, the Nintendo Wii blows me away even though the graphics are positively retro these days. Even though the Wii blows my mind I haven't bought one, but I will. I just know it (unless I die tragically soon or some other such malarky).
Although I haven't messed with Cedega or much with Wine, you're not going to get a great gaming experience running a Linux OS -but that doesn't mean you have to totally go without. There're some decent games in your repo's and I'll show some off here.