I haven't tried Victoria yet, but I have done Arsenal of Democracy, which is a sort of mod for HoI2.
Compared to Arsenal of Democracy:
Much, much more complex reason-for-war system. Rather than just belligerence, you must have actual Casus Belli. That dude has some of your historical land that is still cored? Reconquest! That dude is embargoing you? Make him pay (literally) for that! Your ally is at war with some dude(s) but he's part of a different alliance? Well, how about an intervention?
A MUCH longer time period. Stretching several hundred years. From swords to guns. Start ANYWHERE ON THAT TIMELINE THAT YOU WANT TO START ON! Don't want to start on September X? How about starting on September X+1?
Units and combat are much less complex. They do not have attachments. Units have to be in the same place to help each-other. Supplies don't exist. Though there is Attrition.
Territories/Provinces are much more complex. Manpower, stability cost, population, trade goods and taxes...
Resources play no part in construction of units or buildings. Just cash.
Much more interesting diplomatic options. Royal marriages, claims on thrones, warnings, insults...
Actual colonization. Colonize North America with Naples! Or colonize Australia with China! Watch as all your colonies revolt in about 1750!
Generally more conflict-likely world. Kingdoms OFTEN get into fights.
Lack of historical things happening! While you may think this is bad in a way, it can be kinda funny when the USA revolts from a Sunni Morocco and ends up a One Province Minor in Mexico. Plus, this increases the "what if" factor A LOT.
Technology research in EU3 is a lot less complex. It's also linear.
So, this means that they play like this:
HoI2: Historical-ish complex combat simulator over WW2 and early Cold War only.
EU3: Flexible Kingdom simulator over hundreds of years.
Note, this review is a little biased towards EU3 since I love EU3 much more, but this is just my view of it.
If you still can't make up your mind, watch an LP or something.