As a paladin most of your strength is around 4 cost, you have Consecrate/Truesilver Champion/Blessing of Kings/Hammer of Wrath and neutrals like Yeti/Defender of Argus/Twilight Drake/Dark Irong Dwarf/Shieldmasta etc. Early game doesn't mean a lot to you in the long run.
Turn 1/2 generally aren't all that important, I'd say a good 9/10 times I'm passing and hero powering. The only time your opponent will take advantage of this is against a rush deck, and generally you will get more value out of your cards then them and they won't kill you by turn 4. At that point you start playing down really big threats to them and they either take 'good' trades for them (2/3:1 for you) or let you take the best trades for yourself.
The earliest plays I make in either of my paladin decks are Acidic Swamp Ooze if my opponent was a warrior and played a fiery war axe, or was a weaponless class (Mage/Warlock/Druid/ and usually priest unless they mindvision a truesilver). Otherwise the only low cost cards I run at all are Hand of Protection/Argent Protector (Only played for GREAT trades or to feed a Blood Knight) Argent Squire (To feed the blood knight) or a Faerie Dragon. I don't take many because unless they have a secondary use, they become dead weight past turn 3/4.
These are my current paladin decks:
A lot of the cards are harder to craft/pull, but they should give you a better idea of what kind of strategy I run on the curve. I avoid too many high/low costs that can be dead cards on the wrong turns, high costs especially with tons of priest 2xMind Control match-ups ATM. (Its being nerfed from 8 cost to 10)
*edit*
Actually realized I haven't touched my first paladin deck since I started crafting more cards, it was based partly on a deck I read about with some substitutions. There are a few things I would actually change about it now... Anyways, if you look around there are tons of "Master 3* Basic Card Only Class X" decks online that you can learn from and edit to match your play style.