I think both of these games had their problems on release but their expansion packs made them awesome, so no matter which you pick I would aim to get the expansions. Otherwise, you will need mods to help fix balance problems.
Both HoI3 and V2 are sandbox-type games like all Paradox games but they are a bit more constrained by "historical realism" than than EU3, where single-province minors can conquer the globe. I'd pick based on whether you want something that is more of a wargame (HoI series) or a civilization-like game where warfare is a component but you are also building a nation (V2). I'm gung-ho about Vicky--industrialization, mass politics, colonization, diplomacy, and the most recent expansion really fixes up the supply and occupation system so late-game wars aren't as terrible.
EDIT: The posts above mine are also good--I'd recommend shifting slowly into the Paradox world with the EU series like I did, otherwise they can be really intimidating.