Well, as an update, I have started.
Here's my overall plan:
1. use the existing game engine, with the least amount of modification.
2. the tutorial will be a mostly-predetermined-game.
3. each "tutorial message" has an "exit condition", that, once met, you will get the next message.
4. sometimes the ex con is just "time passes", sometimes it's very specific.
Some examples:
(format: step number, text, exit condition)
43
Now what? Take over the galaxy! But how? Build ships! Play for a while, see what you can do.
1012
`
44
OK, things are about to get crazy. You need to either destroy or invade all of your enemy's planets. Research all the technology you can, then we'll build more ships.
99
`
Exit condition "99" is just "wait 10 seconds". but 1012 is
If (all_planets_are_colonized OR Treaty="Open War")
whenever these conditions are met, you get the next tutorial message.
I'm coding it now, we'll see how it turns out