I wanted to jump in here because it's an interesting topic to me, but with the huge disclaimer that I've barely had chance to play AI War yet so it's possible some of this might be speaking out of my backside as it might be hard to apply to AI War.
But regardless, there's an interesting dichotomy here between what we're actually calling a 'tutorial'. It's been said that some very successful RTS games had bad tutorials. But with most modern RTSs, the 'tutorial' in the menu isn't the real tutorial. It's the mission-based campaign. Starcraft 2 basically takes this to extremes, with each mission showcasing the abilities of one particular unit (and fails as you never get a chance to use all these units together to take down the enemy as they introduce the last unit and then it's the end, pretty much).
The question is can you teach what's taught in the tutorial, but in a more interesting way through a series of story-driven missions that make the learning more interesting (and therefore, work better). It seems the answer is yes, but it'd take a long time for no real benefit. Well to throw something out there, why not make that part of a mission-based campaign. Each mission could highlight different game mechanics, and by limiting the units available to you, and having highly specialised enemies, you could force players to develop new strategies. Played on easy/medium, they'd be a tutorial. On hard+, they'd challenge even hardened players.
Of course, that'd take even longer. But, I'd buy that as an expansion. Perhaps it could even be sold as a standalone AI War Lite, with an upgrade available to the full version if people want more. That's where I'd see your ROI. I might be entirely wrong of course, and there's still the fact that that's not really the sort of game Arcen wants to be making. I'm also quite aware that you don't *need* to pull in a lot more customers, the game has sold very well. But I reckon you could, if you wanted. And that could be one way to do it.