After the recent reddit post to state the original Half-Life mod Natural Selection is coming to Linux, I decided to poke to developers of Natural Selection 2 for details of a Linux version!
The game is a hybrid of RTS/FPS so you have people running around as the marines for example, while another will be the commander sat in a little hub telling people what to do! It works rather well.
So there you have it, who knows by the end of the year we may have NS2 on Linux! I have tested a bit of the game previously and the graphics are awesome, the game play is incredibly fun too!
Until then though for aliens vs marines you can check out Unvanquished which is very similar although a lot faster paced (sadly).