Milennia has a mildly interesting approach, where you can settle or conquer cities early on, but to turn those into productive cities that you directly control creates a maintenance burden that is extremely hard to afford in the early game. Otherwise they just give an incredibly small passive income.
Avid Civ/Paradox-Player here as well. I've been banging my head into 4X design for a while as well, and it's hard. In the somewhat classical formula Civ, Master of Orion, Stellaris and such provide - and even many RTS, it's always the same situation as you have in chess: The better executed early game usually wins.
And strangely enough, in a chess middle game, you have better comback opportunities. In Stellaris, you can at times lose a fight, but if you have enough defenses left and sufficiently more production than your enemy, you still win, just slower than you might have. In Starcraft, you may be able to pull out of a bad fight, If you can, and have good production, you stay ahead. Giving back a piece advantage in chess is a much bigger deal and a much bigger loss.
From there, I can't help but think that many, many 4X games in the classical formula boil down to the right few choices in the early game and then it's about correct execution/conversion. And I haven't really found a way around that.
Or, rather, a way around that is to make the situation asymmetric or rather to change the formula. They are billions comes to mind, or Against the Storm. Don't fight equal and similarly shaped empires, but something else.