So my first theorycraft deck for this expansion because I usually gravitate toward Paladin (over 2k wins), and these new cards got me a little excited (still not preordering).
Recruit Paladin
This is just a shell of an idea obviously.
Because "Call to Arms" Recruits 3 minions 2 or less, need to be considerate if we add 1-drops. I'm thinking not. Had "Lost in the Jungle" for combo with Level Up, but I think Drygulch Jailor might be a better fit for getting dudes. It's a deathrattle, so although it's a 1/1, the effect will payoff later where you can have a 1 mana dude waiting.
Also considered Smuggler's Run, which will probably make the final list once I cut the trash. But right now it's a borderline meme deck.
For two-drops, right now there are 12 2-drop minions... Need a lot for Call to Arms to not be too worthless, as you'll want to keep some 2s on the mulligan etc. Duskboar is a wtf-cut it minion for sure, but I thought it added to the meme potential.
Dirty Rat, Millhouse, and Cho are all risky. If you get Rat/Millhouse in your starter then you get kinda fucked. Cho can screw up your Kings/Steed turns... So possibly all get cut eventually.. maybe Rat stays if you add another Equality & some Aldors.
Only 1 copy of Level Up right now, because with Kings, Steed, and Call to Arms, there are already so many conditional spells. Level Up might just not work in this style deck, which means also cutting Jailor probably. I was thinking Jailor+Smugglers Run+Level Up could be some nice combos, and the dudes from Jailor do give you a 1 mana dude in a pinch for Kings/Steed/Bonemare.
Zola seems made for Paladin.
Can add another stonehill / tarim / lynessa / bonemare on same turn if necessary, or if lucky, tirion next turn.
Juggler seems nice with Call to Arms since you might get some juggles when played, but might not be too good after since this isn't really a flood deck, probably gets cut unless Lost in the Jungle or Stand Against Darkness is added...
I actually don't have any weapons in this list, which is bad, need to add something.
I've been toying with the idea of adding the new weapon because you might get some nice effects on your flooded board (after call to arms), but it's kinda worthless if you can't combo, or just do standard Rallying/Truesilver...
Anyway, that's my theorycraft of the day, will change a lot before I actually test it... namely the 2-drop list needs refinement.