NETHACK!
that is all you will ever need.
Well, I don't like nethack much anymore, but
IVAN (Iter Vehemens ad Necem: Violent Road to Death) compiles under linux with some minor modifications, and it is one of the best, most complex and hilarious roguelikes. Don't get me started on all that can happen in that game... so much more than other roguelikes! Also, ADOM and Dungeon Crawl: Stone Soup are two awesome others!
And another vote for Liquid Wars is also pretty fun
Also, Windows games that run on OpenGL can work quite nicely through Wine under Linux. IL2 Sturmovik runs like a charm, and you can even connect to some online servers, use joysticks, etc. Ah, and there's that game I don't stop mentioning,
Altitude.
I almost forgot, now there's also
NAEV, a 2d space shooter. Not very complex yet.
I keep up to date on all of this through
www.happypenguin.org