Pues entre estos días de vacaciones estuve buscando un juego nativo para linux y encontré Glest, el cual esta bajo la licencia GPL y se encuentra disponible para cualquier Sistema Operativo.
El juego es una mezcla (para mí) entre Age of Empires y Warcraft, de hecho el juego me recuerda mucho a Warcraft II pero con gráficos totalmente 3D y claro, personajes, razas y construcciones diferentes.
Los requerimientos de hardware son menos a los que aparecen en la página, lo único es que debes tener configurado correctamente el video3D, los gráficos son buenos, se pueden bajar mapas de Internet, e incluso bajarse un editor de mapas gratuitamente.
Como punto negativo, es la falta de multijugador y que los mapas se parecen todos en cuanto a los gráficos, por lo que puede ser aburrido este aspecto, sim embargo es un juego que les recomiendo.
Actualización al 23/04/2012:
El proyecto ha cambiado a MegaGlest