This is gonna be a tough one because I actually didn't play much of the game, but hopefully this small segment is enough to identify it.
It's one of those games of that era that incorporated transparent green-screen videos on a static background, kind of like
Connections. It was a first-person point-and-click adventure with educational undertones.
As for the identifiable features, the setting of the beginning segment at least was a sort of ancient golden age Venice-type city, what with rivers for streets and everything. You click to move from screen to screen. One of the first people you meet is a tribal-looking two-headed guy. The characters are static until you pick a dialogue option and then their response is a short video clip.
I'm sure this must have been from the 90's, but since I'm not absolutely certain how old I was when I played it I suppose it could've been early 2000's, but that wouldn't quite align with what my impression of the style was. It was on a Windows PC.