I wonder, how to integrate a story (storyline of some sort) into 4X? I find it especially difficult to tie the story with the 4X mechanics (how the narrative connects/interacts with the rest of the game which is a strategy).

For example in Endless Space 2 you have this predefined main storyline (one per race) where you are presented with a series of chapters (disconnected, linear, presented one by one) where you always have 3 options (3 tasks to choose from tied with a reward) and to proceed the stoy you need to finish one of those tasks (4X style: spend X of resource Y, collect X of something, go to location X, etc). Which is kind of, well, not good at all

This is an open question, feel free to interpret it any way you wish, I just wanted to research this topic

If it's a matter of creating progression... You are the offspring of the ruler of the empire. It is time to take you under the ruler's wing and you are given partial reign over the empire. On some measure of success (or just by not loosing miserably), additional territories, capital, or contacts are rewarded to you by the ruler expanding your capabilities. Or perhaps such things become available to you through some means of intrigue.

But in general, I'd expect the game itself to be the story with any dialogue and game progression in effect being the narrative. A so called "mission" just opens up through game events and the player takes care of it or fails.

Though it might be interesting to have an analysis of the player's successes and failures (perhaps measured by growth and loss) presented perhaps through some kind of news service within the game. Which might also might be a conduit for exposing other opportunities or situations through out the realm.

Typically, a story is about people and a 4X game is about empires. This gap is very hard to cross without serious compromises, such as the impersonal and rudimentary "stories" of races in the OP or focusing a 4X game on characters in order to have something happen to them.

A game series that has done something similar is A Valley Without Wind.  In that series, you have a character that's running around, rallying the troops and such, and the plot progresses when the rebellion building hits certain milestones.