I recently picked up Fire Warrior and have been extremely impressed with it. The levels are huge, there are some fantastic voice actors in there, the graphics are top-notch and some of the ship designs remind me of FreeSpace capital ships! 
Seeing as I had never heard of this game before picking it up, I was very pleasantly surprised with it! (Published in 2003)
Edit* BTW the link above says the game is spread over 21 levels, however, some of those levels are split into three sections so there are actually more levels, the game autosaves after each section. Oh and I'm playing the PC version always best for FPS games. Anyone played this little gem?
Being a Tau player on the few occasions I ever play 40k anymore, I've long considered getting that, but I've heard it's rather lackluster. And in any case it's a little hard to come by these days.
Ground Control
Ground Control 2 (Better in a lot of ways then World in Conflict, which is very much its direct descendant.)
Steel Panthers 3 (Unlike the other Steel Panthers games, 3 is more a "grand tactical" game then a tactical one; you command larger forces over greater areas. It also, I think, has a more forgiving nature than SP:WaW or WinSPMBT. Also unlike any RTS ever made, this will teach to you a true soldier's respect for artillery.)
ORB (Homeworldesque, but compelling, with decent gameplay. It's not a Homeworld clone, though; Homeworld was much more forgiving then this.)
Morrowind (Story-wise, gameplay-wise, complexity-wise, creatively-wise, Morrowind is simply head and shoulders above its descendant Oblivion. Perhaps Oblivion's expansions helped, I don't know yet, but they have stiff competition from Morrowind's expansions too.)
Sincerely recommend skipping Homeworld 2 unless it's for mods or multi. The SP campaign is a *****.