Which Paradox strategy games to start with?

Pfft, hop on that Mount and Blade

The easiest to figure out of the 4 is probably Europa Universalis. Vicky 2 takes a lot of economic micromanagement but even without the expansion is a lot of fun (though it does vastly improve the game). Crusader Kings 2 is also pretty easy to pick up once you figure out how all feudal stuff works.

Europa Universalis 3, it's the easiest and most entertaining ,it also has the longest timespan , best Grand Strategy game ever made

EU3 is by far one of my favourites, although once your used to the game it lose's the majority of it's challenge (Did anyone ever see the retail collector's printed manual? It was HUGE). If your into lesser (i.e. not as grand as EU or Vic/HoI) then Swords of the Stars 1/2 has plenty going for it as a 4X Strategy Game. Couple of friend's of mine has had a game of SotS2 going for 4 month's now, it's a insanely good game once you get your head around it.

Well I was going to say Warlock, but you don't have that one :<

I only have CKII. It's not all that bad, having just spent an hour in the tutorials (only got through 2/3rds of the beginner tutorials lol). The hard thing is figuring out how you're doing, I spent an hour or two into a campaign and I'm not far enough in to tell how bad I'm doing

EU 3 or Crusader Kings 2
Sengoku is fun as hell too

Crusaker Kings 2 is probably the easiest. It allows you to play as noble, who only has to take care of his/her province(s), and not worry about the bigger picture all that much, at least not early on. While there is a lot to actually learn if you want to get really successful, in order to just play & enjoy the game, you don't need to know a whole lot about CK2.

Victoria 2 is probably the hardest one to get into, as you always need to think long-term, and most things you do don't have any direct results. It is my favourite of the lot, but I would recommend waiting with it until you are at least familiar with the sub-genre.

I always found EU3 to feel a bit too abstract. It is not "that" complex, but I found the others more straight forward.

And finally, if you want to play HoI I would actually recommend that you play HoI 2 first, for the simple reason that it is more approachable. HoI 3 brings a lot to the table, and it can get overwhelming. On the other hand HoI 2 is relatively easy to get into (though it is still a complex game).

EU3. I'd buy the other two expansions, though, they very much change the game. Otherwise, Vicky II if you want more politics and economics or CK2 if you want more dynastic interaction.

Dunno who told you that Vicky 2 is easy to pick up, but they were wrong. If you're willing to invest a couple of hours to get a grip of the underlaying mechanics, yeah it gets easy, but it's not noob friendly. Go with EU3, then pass onto CK2.

Although you don't own it, you should try Warlock: Master of the Arcane, it's very similar to Civ and it's very easy to pick up. though the game isn't really too difficult even at the higher difficulty levels, so it's not much of a challenge.

I'd say Crusader Kings II. Fairly accessible, and one you can enjoy, and learn as you go along, without feeling overwhelmed from the outset.

Victoria II, as has already been mentioned, is a more traditional Paradox game, and fairly tough to get into, although as with the others, rewarding once you [eventually, many hours in] feel you're starting to get to grips with things.

Majesty is awesome.

EU3 or CK2 imo.

I never really liked vicky 2 going from eu3.

MAGICKA!!!!!!

EU3 is the simplest of the Grand Strategy games. Then CK and then Viccy. CK2 is a lot easier than CK1 though.

HoI is a little in the middle because it's mainly an army composition and tactical game. Magicka is not a strategy game and Majesty is simple but weird to play for most RTS players.

Personally, I started with HoI2 and think it's the best game Paradox has ever made, especially after you include Darkest Hour.

Edit: Also, HoI2 is REALLY simple once you actually look at it.