I can vouch for Crusader Kings, Hearts of Iron, and Victora (all from the same developer as Europa Universalis: Paradox Interactive) as having the kind of beyond-Civ levels of depth and complexity you're looking for. Each is tailored to it's own slice of history in a way that Civ by nature can't be.
While I have never played it, I have heard good things about the complexity of the Europa Universalis series. IF author Adam Cadre wrote a mini-review of it a few years ago:
Re:The Brilliance of Dwarf Fortress
by jonnathanson on Friday July 22, 2011 @07:46PM
(#2795620)
Have also heard good things. Given that I keep hearing them, I think it's time I got off my butt and checked it out!
I think there is a niche -- albeit probably a very small one -- for more super-hardcore strategy games in a variety of settings and genres. Folks like me would love to play a game like Civilization and have incredibly rich, complicated diplomacy and trade and other issues that simulate, as closely as possible, real-world geopolitical issues. (In some ways, for instance, I'd love to be able to fight a cold war with an AI opponent, rather than an actual war).