Decks for New Players: Red Soldiers
Updated Version 8/8/18
Red Soldiers is, in my opinion, the best deck in the game for beginners. It's a tier-1 aggro deck that can be built mainly with commons and uncommons, and you get many of the cards required from the Order and Rage starter decks. I have a lifetime winrate over 80% with Red Soldiers, and at one point I won 35 games in-a-row with it. Players have adjusted, it can be countered, and it's not as dominant now as it once was - but this deck will always have a place in my heart. Here's my current version, but there's plenty of room to put your own twist on it.
You're almost always the beatdown deck, meaning you need to win first. You want to play aggressively, maintain board control, and end the game around turn 6. If the game goes much longer than that you're likely to lose.
You're using Basic Alexa, the first hero you get when you start the game.
The Creature Curve
Your first level will be Order (gold) and your second level will be rage (red). You're usually going to get your second level when you have 2 mana or 3 mana.
1 Drops: Ideally you want 8 one drops: 4 steelhost spearmen and 4 sentry of the light. The other order options are relic guard and pegasus...and they aren't good in this deck. Put in as many steelhost spearmen and sentries as you can - and if you don't have 4 of each, put in more of the 2 drops.
2 Drops: Order has a bunch of 2-mana soldiers. They all work in this deck, and ideally you want about 8 of them. If you don't have as many 1 drops, you can play up to 10 2-drops.
Steelnor innkeeper is probably the best 2-mana soldier. Play as many of him as you have. After that you can fill in with Dwarf Spellbreaker (best IMO), Dwarf musketeer (not as good at high levels); Temple Guard (best if you have 4 sentries of the light); or Heavy Infantry (not that good). As long as you have some combination of these that adds up to 8 cards in your deck, you're in good shape.
3 drops: In this slot you'll have both 3-mana, one-aspect cards and 2-mana 2-aspect cards. It's the place with the most flexibility in the deck. The non-negotiable is 4 Elite Vanguards. After that, put in as many cavalry field captains as you have, and as many Knight recruiters as you'd like. You can have up to 12 cards in this slot (4 of each), but I usually like to aim for 10 (4 Vanguards, with CFC and Knight Recruiter making up the other 6)
4 drops: There's one creature in this slot - master tactician. Put in as many of him as you have, up to the maximum of 4. He's the most important creature in the deck.
Spell and Artifact Options
You're got flexibility with your spells and artifacts. Usually you'll have 12 of them. 8 are pretty much non-negotiables:
4 Fireballs: It's why you're playing red. You want fireballs.
4 Guards Guards: You're playing soldiers. This provides great versatility.
The other 4 spell/artifact slots are flexible. You can consider Massive Assault, Insignia of the Sun, Forced Labor, Fireblast, and Cannonade. Some people also play touch of light, pacify, or even lightning bolt.
You want 19 of them. 8 rage shrines, 7 or 8 order shrines, and 2 or 3 soldiers memorials.