I wouldn't recommend HOI3 as a first Paradox game. I've probably played it a similar amount to CKII (about 50 hours), and still hardly know what I'm doing most of the time, even with the HOI3 Wiki. Of the most recent 4 Paradox grand strategy games, the only one that I'd consider comparably complex/hard to understand is Vicky 2. And the in-game tutorial in HOI3 is pretty miserable.
On the other hand, I've successfully introduced real-life friends to Paradox games from Civ/Total War via CKII and EU4. Combined with the CKII/EU4 wiki ready for Alt-Tabbing, and it's doable (like Lohrenswald, I'm not really one for YouTube videos to learn games) without the help of a friend who's already into it, though that certainly helps. Overall, I'd recommend EU4 without expansions as a first step into Paradox games coming from Civ, starting out with someone like France or the Ottomans who can tolerate mistakes.
In terms of ease of use, I'd rank recent-ish Paradox games in the order EU4, CK2, EU3, Vicky2, HOI3, though 1/2 and 4/5 are somewhat subject to preferences/past experience. So unless someone was coming from a hardcore wargames background, preferably with a focus on WWII, I wouldn't really recommend HOI3 as the first game.