I just watched Terrence Malick's The New World and now I have a terrible urge to play this game :/
I never played through the expansions, but I just remember that the storyline of the main single player campaign was awful. It was like a really cheesy, poorly written, educational game.
I also remember the AI being pretty stupid. But it's been years since I've played it.