I hate to sound anti-constructive, but wintendo boxes run games better than linux does. Cedega, let alone the WINE project, have made great strides into getting windows apps to run in the linux environment. To be blunt, however, the focus for linux gaming should be in full ports and not "virtualization", "emulation", or "API Hacking". Games will never be "good enough" in the linux environment until they're programmed for it. Plain and simple.
I have gotten games to run with usefulness in Debian and Suse 9.2:
Day of Defeat: Source
Half-Life 1 & 2
I realize those are all from the same genre...but here's some factors that I think may help you increase your playability.
1) Try using WINE instead of Cedega. I was able to get CSS running in WINE before I ever got it running smoothly in Cedega. Documentation is your friend.
2) Hit some good places like linux-gamers...try googling for WINE tweaks...
3) Use the most stable(not necessarily the most up-to-date) drivers...especially sound and video.
4) Try an older version of Wine or Cedega.
I've tried gaming in linux with Debian, Slackware, Mandrake, Suse, and Fedora over the last year with varied results...seems like everything is a huge factor and each different(software or hardware) will change the performance either way. For instance...using the most bleeding edge video drivers does no good if you're running with an old kernel.
1gig 533mhz ddr
80gig 7200 hd
ATI x300 128mb
Asside from the rant I hope this helps.