Hearthstone does a WAY better job at this with powerful removal spells
that you get right from the beginning, fair RNG effects and with the
Tavern Brawls, where everybody can have fun.
Sorry, but I have to strongly disagree @ Hearthstone doing a better job for new players.
It's just that Hearthstone is much easier to learn, because you actually don't have to learn as much. This doesn't mean it makes a better job, but it's just a much simpler and more casual game. Most of it comes from the simple and, placementwise meaningless board of Hearthstone, while meaningful decisions are often replaced by rng-stuff. Not much to learn there.
As much as I like the idea of having a more strategy-focused card game, it's really hard as a newbie in Faeria and I'm losing interest in the game pretty quickly...
However, I agree on your point, that Faeria could use some more tutorial-like stuff: The game is way more complex than other card games, so it needs more tools for new players (especially casual ones) to learn it. I think the codex-quests are a good start for this, but not more.
One way to improve this, could be npc-challenges (like in Scrolls, for those who know it): You have a list with specific challenges, which confront you with a preset situation on the board. You know, sometimes with a deck you build yourself and sometimes (for beginners) with a preset deck, maybe even a preset hand and draw on the following turns. This way, you can teach new players the different possibilites to react on specific board situations, they are otherwise overwhelmed with.
The goal of these challenges also shouldn't always need to be "destroy your opponents orb", but maybe something like "build a land on spot X, Y and Z within a set number of turns", "don't let your opponent touch your orb for X turns" (while you get taunt creatures and have to face charge/haste/jump etc.) or stuff like that (you get the idea).
Such challenges should also reward the player for completition based on their difficulty (packs? pandora coins? gold? avatars/orbs etc.?).
Regarding the fullcollection, Faeria assists new players way better than Hearthstone already (which, I admit, isn't hard).
Faeria: basically one pack/per day due to 10g/win (20 for the first) and 60g/quest, while having like 1 epic every second pack, 1 legendary every... 15-20th? (maybe I was lucky with this, though)
Hearthstone: basically one pack every second day, while having like 1 epic every 5-7 packs and 1 legendary every 25th-30th pack (yes, I kept track of this). That bonus pack for each week's tavern brawl feels totaly laughable in comparison, especially considering that you just get 40 dust (4 commons, 1 rare) out of it pretty fast and most of the time.)
So in conclusion, I think Faeria much more playable without buying the full collection than Hearthstone is. If you start the latter today, you can spend like $300+ for packs and even then you won't get close to a full collection.