Master of Orion 3 is the winner IMO. Moo3 makes every little thing very hard to manage, and unrewarding. The time it takes for a fleet to traverse the stars often means that your fleet will be several generations old by the time it arrives, and the game grows in scope as the turns go on and becomes unmanagable. Civilization did as well, but it was easier to understand as it wasn't theoretical applications of astrophysics that were the topic at hand.
Dwarf Fortress is actually kinda hard but because it was never on a game store shelf, I feel that imagining it done professionally would yield a game about as difficult, and as polished as SimCity - that the difficulty is from the lack of polish, and poor graphic quality. I don't want to give it the top spot.
Romance of the Three Kingdoms in most of the incarnations in which I've seen it, is rather
overly hard to understand and play. Often it starts out with absolutely no explanation of what is going on.
Defense of the Ancients...I have to mention this because it has a serious learning curve, and the online Battle.net community are some of the biggest assholes - and racists - I've had the displeasure of ever encountering. Are you new? Don't know what items to buy or where to buy them? Ask what an abbreviation means? Don't know what specific abilities one of the 96 heroes an opponent may have chosen does? If it comes out then expect to be kicked from the game.
Die a couple times, and they'll cuss you out and ban you from ever playing with them.
They ping you greater than 80 ms? Reason enough for a kick. And the game punishes death in many ways. First, you aren't on the field, gaining experience, for a significant portion of time. Second, your death gave the enemy experience. Third, you lose a significant amount of money, which the opponent gained. All of which means, if you die once to a player, you have a near-zero chance of beating the player in a later battle.
Each of the above games I have actually quit due to the learning curve.
Eve Online is difficult to learn and master, but significantly less so than other games mentioned. Plus the community help channel will answer many of the questions people have - although asking for help may make you a target to a scammer! But still, it's no walk in the park. You can expect to lose as much of your assets as you risk, (hopefully) learning from your mistakes as you go. It deserves an honorable mention among this worthy crowd.