Europa Universalis II released in 2001, a year after the original Europa Universalis, and was essentially an improved and expanded version in a variety of aspects. As such, there really isn't any point in playing the original EU. You'll be able to satisfy your taste for warfare, but there are also plenty of other systems to experiment with, while still not being overly complicated.
Hearts of Iron (2002) is, of course, completely focused on the Second World War, and should only be played if you specifically want to play a WWII strategy game.
Victoria (2003) covers the 19th century and therefore has much more complex economic and demographic systems, plus internal politics. You can still find plenty of wars to have fun with (colonial wars, refighting the American Civil War, national wars in Europe, WWI), but it's probably less focused on warfare than any of the games covering other time periods. I'd recommend trying this as your second game after EU II.
Crusader Kings (2004) was originally supposed to be developed by a Russian company (the same one that distributed Paradox's games in Russia). Although the developer kept promising that significant progress would be made after "just one more sushi dinner", it never seemed to get anywhere, and eventually Paradox terminated that agreement and finished the game themselves in somewhat of a hurry. Perhaps try as your third game, or fourth if you prefer WWII to the Middle Ages.
Diplomacy (2005) was created via contract with Hasbro, which had acquired Avalon Hill's intellectual property. Paradox was never able to develop an AI at all capable of playing Diplomacy, but nonetheless insisted on maintaining an interface in which players could only communicate with each other by applying symbols to a map, apparently with the notion of putting AI players on an equal footing with human players. I don't know whether it was Hasbro or Paradox who were responsible for this dreadful idea, but in any case the game was released on an apparent deadline with a brain-dead AI. It was essentially worthless except using human players only, and the human players were constrained to the limited means of communication until Paradox finally relented and added text messaging in a patch, something which had been suggested to them while the game was still in beta-testing.
I suppose you could look at the even earlier games in the Svea Rike series (or Airfix Dogfighter) but I don't know much about them.
Since Paradox gradually declined after 2003, I wouldn't recommend any later games, except perhaps Victoria II (2010).