There are a number of very good rep rewards available for paladins, particularly Protection and Holy paladins. I thought I’d do a bit of a rundown for those who are levelling a pally and haven’t identified their faction goals yet. If you’re a holy paladin in pre-raid gear, you might want to aim for:

Honor Hold/Thrallmar – Revered.
For Ring of Convalescence/Ancestral Band and Glyph of Renewal at Revered. (Sage’s Band/Farseer’s Band at Honored is a nice addition to your DPS set, too.)

Cenarion Expedition
You can actually skip CE faction if you’re purely Holy, unless you want Windcaller’s Orb (at Exalted) until you get a good healing shield. I wouldn’t recommend it personally – but hey, some pallies wear cloth, too.

Sporeggar
Nothing for you here.

Aldor/Scryers – Exalted.
For Greater Inscription of Faith (for Aldor) or Greater Inscription of the Oracle (for Scryers) at Exalted. (You can use Inscription of Faith/Inscription of the Oracle (Honored) until you hit Exalted.) Aldor also offers Vindicator’s Hauberk (the best pre-raid tanking chest) at Revered, and Medallion of the Lightbearer at Exalted (although there are better-balanced pre-raid neckpieces out there, this one does have good base stats). Scryer-aligned paladins can get Seer’s Signet at Exalted, which is very good for a shockadin set.

Lower City – Revered.
For Lower City Prayerbook, an excellent trinket for paladins that many prefer over epic alternatives. Gavel of Unearthed Secrets at Exalted is a good shockadin mace, too, and if you’re building a tanking set it’s the best tankadin mace you’ll find until raid or arena gear.

Kurenai/Mag’har
You can pretty much skip Kurenai/Mag’har faction altogether, from a paladin point of view.

The Consortium
You can skip this one, too.

Keepers of Time
For a pure Holy pally, you can skip KoT faction too. If you’re going to be doing some tanking, I’d recommend aiming for Revered for Timewarden’s Leggings and Glyph of the Defender (and Continuum Blade until you get to Exalted with Lower City for the Gavel).

The Sha’tar – Exalted
For Gavel of Pure Light, an excellent healadin mace (I got a Hand of Eternity crafted before I got to Exalted Sha’tar, but the Gavel of Pure Light isn’t far behind it). You might also want Crest of the Sha’tar (Exalted) for a tanking set, and Xi’ri’s Gift (Revered) for a shockadin set.

Ogri’la – Revered
For Apexis Cloak. Ogri’la Aegis (Revered) is a good tanking shield before you hit Exalted Sha’tar, too.

Sha’tari Skyguard
You can skip this as a healadin. Airman’s Ribbon of Gallantry (Exalted) is a decent shockadin trinket, though, when you consider the fact that you’re likely to be playing as a shockadin for solo content only – grinding and questing.

Netherwing
You can skip this too. Commander’s Badge (Revered) is a nice tanking trinket, though.

Shattered Sun Offensive – Exalted (New in 2.4!)
For Shattered Sun Pendant of Restoration, which is an amazingly good pre-raid healing neck. Shattered Sun Pendant of Acumen (Exalted) is also good for a shockadin set, and Sunward Crest (Exalted) may suit tanking pallies for threat generation.