Including the word 4X, or even including the word Hex or similar, is something I've considered but seems like it would be awkward in most cases.
Regarding tying the name of the game to an existing title, there is definitely a risk of alienating people who don't like the game. But then again, we have an opportunity to pull in people who did like it. Still, those people would be swayed by "it's another strategy game by Arcen" if they are going to be swayed by anything, so preaching to the choir there most likely. So perhaps not having the word federation in the title at all is a good idea.
I need to find some short stories that are sci-fi online and run them through the word-cruncher and find interesting words. Right now I feel like the pool of words that we're using isn't robust enough.
Mal: I like where you are going with a lot of your thinking, and it's very creative. I want to avoid overt religious references, though. Having references to the fact that there is this huge sentient planet is something that would be very cool, but I want to avoid comparing him to God for... reasons that will become clear in the game.
I'm also looking for something brief and kind of... elemental, I guess you could say. That tends to mean that the longer the title gets, the less general it becomes. "A Valley Without Wind" is very specific. "The Lord of the Rings" somehow strikes me as less so. "Star Wars" is really very nonspecific. "The Last Federation" is very much on the nonspecific end, too. "Pushing Ice" or "Foundation" or "The Vorkosigan Saga" are all nonspecific as far as I'm concerned, too. The last one does have a proper noun in it, but it has a sort of sweeping feel to it. Much moreso than "The Warrior's Apprentice."
I'm not sure if I'm making any sense with that last paragraph or not. To some extent it's an "I know it when I see it" sort of thing. And also, will it fit on a tiny, tiny steam capsule.