My Opinion: Definitely go with Victoria II
Crusader Kings II - Crusader Kings II is a wonderful game, and is rightfully deserving of the love it has received. It is a much more flavourful experience and will give you many hours of interesting variety to experiment with among decisions, events, and starting positions. Do you want to rebuild a dead empire and a dead religion? Go right ahead. Want to build King Arthur's dream and kick the Anglo-Saxons out of Albion? Go right ahead. You have a very long time per game to figure things out and see whatever adventures may appear. The vassal management and character mechanics give it a complexity that can become rote at times, but it's still a wonderful game. That being said, this game hands out achievement like candy or not at all. I'm not talking about Steam achievements, I'm talking about the sense of accomplishment you get. You'll feel great as you take a struggling starting position and manage to unite a Breton Britannia, but you'll find very little sense of accomplishment after that, as the ai is generally unable to manage the complex interweaving of relationships and their consequences. If you need an example, go look at some of the empires on the "CKII Empire" thread. The Pope will hand out titles to families that are all heathens except for the one person he gives it to. So be prepared for a long, fun, but ultimately easy game.
Victoria II - Where CKII's variety lies in the difference of flavour among people, Victoria II has a very cookie cutter mold for every nation in the game. They do not play fundamentally different. The real variety is in what the population of your nation is like at start. Want to restore the Byzantine Empire? Good luck, those lands are long since Turkish Sunni's by now. There isn't a quick and easy way to build an empire, and you won't, more often than not. Maybe you're one of those select few nations that's lucky enough to have some flavour decisions, but, otherwise, you're just another fish in the pond being influenced by the kids splashing around (The Great Powers). Victoria II is exceedingly more difficult, and you will groan in frustration as the USA gets its fingers involved in your South American conquests. You'll rage as your supposed allies refuse your call to arms over the fact that they sphered your enemy's vassal. Unlike CKII, the starting positions are not anywhere near equal. However, each and every victory will be a wonderful achievement because the difficulty is so much higher. You won't conquer the world as Ireland, and you won't even become a world power in your first few games, but you'll be overjoyed at anything you manage to accomplish. That being said, it is an older game, and there's a reason that Paradox Interactive's financial success didn't truly take off until CKII (See Post Note). Many of the systems are complex and don't lend themselves well to the U.I.. Some of them are just bad in concept and execution, like the much hated World Market(1). However, I feel it is the much superior game.
1) The World Market is a mechanic where all of the world's goods go to a single market and are then sold based on the priority of your nation. The world powers have first dibs on any and all goods, making it exceedingly difficult for third world nations to get goods they produce!
Post Note: I could very easily be incorrect in this statement. This is based on the fact that I have interacted with people who know what CKII and EUIV are, but have no clue what any of the earlier games are. This also comes from statements of my long-time player friends, who hold such opinions themselves. I understand that this is totally biased, but I have no other competing sources for information on this subject.
I don't know, 5/5 people who've come out in favor of a specific title did so in favor of CK2. :V
Five out of six, nao. :V