Interesting list. I personally found Armada + expansion to be fun but to easy even at the highest difficulty setting.
I've read that the 1.04 patch was supposed to make the AI more aggresive but I haven't tried it yet. Have you played the 1.04 patch? Would you say the AI is better at pressuring you? Just my thoughts.
I can't comment on Supernova 1.04 yet, as I currently don't have internet access at home (and am therefore unable to download it). That should change in a couple weeks, though!
Also what is BOTF? A space strategy game?
As Tophat said, Birth of the Federation is an old TBS 4x game set in the Star Trek universe (primarily during the TNG/DS9 timeline). It's buggy, the graphics are obviously outdated, and the AI is pretty rubbish (especially in the late-game), but it's still fun, despite everything. I would dearly love to see a sequel!
"Evil is easy, and has infinite forms." -- Pascal