The constraints are that nothing the player owns can be modified by the tutorial script. You can send messages, detect what the player does and control an AI's units.
I was thinking something along the lines of:
- Walk your female citizens to the civil centre.
- Gather some resources.
- A barbarian horde is coming! train warriors.
- (AI barbarian horde arrives).
To clarify (thanks Pureon) there are two parts, one is making a nice map and that other is writing a storyboard. The storyboard is more important to do first so it would be great to have someone write that. Once we have a storyboard we could modify an existing map which would be easier.
Also I have attached the example I made which might help give you an idea of how it works.