I started very early on EU and have played all the iterations, although not recently.
The main problem, to me, is less the complexity and more the sense that they have never satisfactorily escaped the sense that it is all about changing the color of the map. My guess is that the Civ players who like EU the best are likely the ones who also play Civ that way.
As someone already posted, EU is also more of a history simulator. Nothing wrong with that, but in my mind that conflicts with the "color the map" goal.
The other thing about being a history simulator is that the game is a little misleading when it comes to your options as a player. In a sense, you are back in some long-past year with all the options that the leader of that country had... But not really, because various events, options, and modifiers are only there if you have the country that eventually went a given direction. Play Portugal and key things will arise allowing you to expand into unexplored territory -- but less so if you are, say, Sweden.
In my mind, though, an extremely important difference is this: EU is trying to do something that is innately impossible. They are trying to re-create the situation of rulers in an era when rulers did not know the value of exploration, nor the most lucrative locations -- but we as players do know.
Civ admittedly has a parallel problem -- we, unlike ancient rulers, know not only that tech advancement has great value, but which techs lead to what kind of value. But at least exploration feels real, and your options feel truly open. So, for me, Civ has much better legs over the long haul.
