Not having played EU4 yet, but I find them to be totally different games.
Could not agree more, or stress this enough.
I saw one post on another forum discussing EU4 stating that the EU series was what people "graduate to when they're grow out of CivV". Unfortunately this opinion is commonplace, and so grossly erroneous I have a hard time wrangling the overwhelming number of opposing truths running around into a cohesive, direct argument.
First of all, while both strategy, they're two different sub-genres (The Civ series is 4X, while EU is Grand Strategy) if you go in as a 4x player, expecting 4x, you may feel constricted by its borders.
As for the gameplay, of course much of it will come down to taste, so I'll just leave out the objectivity and give my personal opinion. Which is to say I don't like it, and have never liked the EU series. Despite many days playing, and trying to like it thinking "I love strategy games, these games are insanely well made by very competent designers... why am I not loving this?". Truth is, I find it to be a stale ride inside the mind of an idiot savant who's been doing accounting for his brother's company every day for the last 40 years.
It is more complex, but not in a way that serves it well. In my opinion, its many systems for empire growth have little interplay outside of "devote resources here, that's less to go there", which pushes it dangerously close to what I'd consider simple convolution. You pick a path, and go. The only thing you sacrifice to do so is not going down another path as much as you go down the one you chose.
In Civ5, You specialize, sure, but there are always factors within the interplay of systems that shake you this way or that, throwing tangible hurdles at you, constantly forcing you into risk vs reward choices, everything has a cost outside of the simple monetary one, and generally the more you spike your growth in one spot, the harder these forces weigh on you, some simple numbers, others interesting and full of flavor.
EU4 does this to of course, it's just not its focus, it doesn't do it nearly as much, or as well. At the end of the day Civ5 creates an intricate web of possibilities, while EU4 is more like the root structure of a really old willow tree.
It comes down to personality probably, if you're the type who like to fine tune systems, and delights in every fraction of a percentage you can milk, you will absolutely adore EU4, I think. And not being so tied down with all the webs between the forks, EU4 can afford to get further in the directions it does go, (diplomacy as a prime example, really puts Civ to shame). If however you couldn't care less about details, and love interplay and how things work together, Civ is the way to go. Though, admittedly, trying to get a feel for diplomatic relations in densely populated corners of the world is very much... ugh... web/interplay lover friendly, it's just a shame that flavor ends with the diplomacy, and doesn't carry over to actual empire management.
so awh... I'd suggest playing the demo first. Well made, without a doubt, just a very niche title.