I wan't to see something that combines group AI with the Sandbox mentality, so instead of skirmishes, you can have two different groups, using fleet tactics against each other, like being one unit in a massive RTS situation, but with freedom of choice, you can participate in the interaction, on either side, you can trade and try to avoid the combat, or you could even sell weapons etc. Massive battles could take place, but they would not be scripted, it would simply be the computer AI battling against itself. If the two are not at war, depending on relations, you could still trade or possibly work as a freelancer for an ally.
The best example I can think of is that the combat side is not dissimilar to watching 2 computer AI's battling it out in a Homeworld skirmish map, but on a larger scale, with strategic points to fight for etc. RTS games have shown this sort of AI is possible, but it's never been applied to a free-roam type game.