There are a few paladin threads floating around about certain skills/talents, but the discussion isn't very focused. Let's make this a single thread like the other classes have and consolidate here.

Here are a few thoughts on specs, both as level 70 in beta and now at 60 on live.

Ret Build: CSadin
I've been playing with this on live since the Tuesday patch, and its basically what I used to level with in beta as well. I tried to test it some in a raid setting last night, but we have been short on healers, so it hasn't been practical most of the time. I think to what Bekah commented on in the shadow priest thread that it is hard to convince anyone to have a healer not be primarily healing on any learning encounter. I think raid groups will want the 3% to crit, but do they really want a paladin in melee gear DPSing and keeping all the judgments up? You could put up crusader in full heal gear and occassionally whack the mob and be just fine, but in this case you've sacked 40x points into a spec you aren't really even using on raids, save for one ability. As far as raw sustained DPS, on Noth I was able to place in with the low DPSers (this while full-time healing during balconies), which wasn't terrible given 0 consumables. On Maexxna it was about 15ish. But of course this is with 15% vengeance and 6sec CS.
In PvP, this build is pretty awesome. I had forgotten how amazing repentance is. With that and CS, it's virtually impossible to lose a 1v1 against anyone save maybe a priest. CS gives you the burst to kill healers, and with 2 interrupts (BE will have 3...) its crazy. If you are full combating healing a team, I feel that the ability to repentance one person beating on you almost makes up for prot/holy talents you might otherwise be able to get.

Prot
Prot is fun for iron-manning (like soloing strath at 70), and enjoyable in pvp as well if you want to combat heal. I haven't seen any paladins tanking anything significant yet, so I can't really comment on the build as far as that goes. Even with tanking greens/blues leveling to 70, my gear is still so far behind any warriors I run with that besides off-tanking an add here or there, I haven't had any reason to have deep prot talents.
There seem to be a healthy number of paladins who love to do the Reckoning leveling build, pulling whole camps of enemies and slowly widdling them down while they heal tank. Its unfortunate the prot changes didn't make it to live so the tree is still pretty weak there, imo.

Holy
Besides the 41 point talent, holy remains pretty strong. I've specced holy to solo heal all the TBC 5 mans and for some initial kharazan sorties, but that's about it. I know many paladins swear by spell damage builds for leveling, but I just couldnt get into it. Even with ~500 spell power it seemed so amazingly slow compared to Ret or even Prot I couldn't stick with it.
Obviously with 14k+ hp pools on tanks at 70, there's a concern about flash of light scaling. Even with a bit over 1000 healing fully talented, you're still looking at 1300ish heals - a bargain for 180 mana, to be sure, but the HPS is just so low I'm not sure it will cut it. The rest of the tree gets you +11% to crit with HL, which is pretty nice, and maybe even necessary to sustain healing. In Kharazan, for example, my group was actually wiping to the Butler from running oom on our first few attempts - something I hadn't experienced in some time. Without illumination it would have been brutal.

Spec Options
So what are the current thoughts on what will be the best raiding specs and arena specs out there? My major concern at the moment is whether Ret will end up being viable in either, or if virtually everyone will end up Holy/prot essentially the same as before TBC.

Not sure how valuable BoK will be in arena. You have to figure you'll be overwriting it on melee with freedom and possibly casters with sacrifice. I've actually been using light sometimes just to add some extra burst healing.

Obviously in raiding you'll still need 1 paladin with it, maybe 2 if you want a backup.

I think I am going to spec back to Prot for leveling and iron manning. Don't laugh, but that is how I leveled from 30 to 60. Flurry Axe and a Shield and Prot spec. The idea was to tackle 5-6 mobs at once and let them die to Holy Shield, BoSanct, Thorium Shieldspikes, Imp Retri aura and my awesome swings for 100 dmg or less XD

I am really sad Paladins cannot use Daggers because I don't want to get a slower Weapon than Flurry Axe (1.5) because it's plain awesome to proc JoW/JoL so much you never have to worry about mana/health while the mobs kill themselves by hitting you.
I seriously think that is OP, and I intend to exploit it as much as I can. :) (I mean, I could friggin solo the last part of Bloodsail Buccaneers while being 5 levels lower; you know how the mob density in the ships is - dense enough that I swore to never do that quest again, but heh, Paladins are an exception :D)

Aaaanyways, enough rambling. What do you say to this spec for leveling and iron manning?

The way I was going to kill stuff is running around with Retri Aura (or Conc aura if I need to heal) and spam Holy Shield with a Thorium Spiked shield while my fast weapon procs JoL or JoW with SotC active.

EDIT: Should I drop Parry for Ardent Defender? Parrying stuff doesn't proc the damageshield.

Why skip reckoning? For AoE grinding, that's a 100% boost to your melee output. (3+ mobs attacking you should keep it up permanently)

You might as well drop the points in Ret and get AD and Reckoning. 3 points in imp. SotC definitely isn't worth a few points in the niftier talents at the bottom of the Prot tree. AD I haven't tried personally, but from duels, heavy Prot pallies are a pain in the rear to finish off. If you like being ridiculously durable, I think it's a decent talent to pick up.

Im going to be a cynic here but, with the way feral druids and shadow priests are shaping up, unless 25man raids only need 4 healers I think most paladins are going to be stuck healing with the shaman and any druids/priests who really like healing. We look to still be the worst of the classess for dps, and provide less utility than a shadow priest or feral druid. In tnaking, we are miles weaker than a bear druid, and behind the game on warriors (though not by much).

Id love to be more optimistic, but to me the new paladin looks to be about as viable as the 1.12 druid. Which is to say, while in tanking or dpsing they are just about viable, and bring a small amount of utility the vast majority of the population will be asked to spec holy and heal.

With that out of the way.
Holy seems to provide more burst controlled burst dps than Ret, and looks to be the strongest for organized pvp. Ret is nice for grinding or some attempt at dps/utility in groups.

To me prot still looks to be the weakest spec, both for pvp and pve.
I expect the vast majority of paladins will be 41 ret from 60 to 70, in much the same way most were ret from 1-60.

Something like this? :)

I do think there will be a place for one Retri Pala per 25 raid. Their own DPS is quite formidable, they also take some stress off of other Paladins with CS, Holy Aura helps healing and the already mentioned 3% crit.
That being said, they can also help off tank better than their Holy counterparts, right?

Hard to disagree at this point. One big feeling I've had with TBC healing is that while on live I have always gotten by with 21 holy (for illum and DF), I'm not sure that is enough to cut it in TBC. Granted, you are suddenly not out-gearing the level 70 stuff anymore, so that may be part of it. But that extra crit % and LG feels pretty necessary if you are taking on full healing responsibilities.

Edit: To clarify, by "get by" I mean I never saw a significant difference in 31 holy or 21 holy with the old talents. I don't run OOM unless I use LOH and the extra 5% crit wasn't worth losing talents in other trees to me. Now you can get 11% crit with HL, 2 second HLs, and more than 100 extra spell power. That's a lot more to give up.

But isn't that the same for every DPS healer/hybrid?

Well, regardless I am pretty sure part of making hybrids raid viable will be the balance of class roles needed for each given fight. One might require more healing, one more healing and another one more DPS, you name it.

Possibly at the moment.
The new shadow priest is bordering on required in its current state, and certainly incredably desireable. I cant imagine any 25man raid running without at least 1 shadow priest. Feral druids are straight up viable either tanking or dpsing and in that way are more desireable than extra warriors at the moment who have to spec deeply and become EITHER tanks or dps. Also mangle from different druids stacks geometrically at the moment, and cat and bear mangle stack with each other, which actually means they stack better than rogues in their current state (which I cant imagine will go live).

At the end of the day there is a minimum number of healers required for any given encouter, that job will most likely be taken up by those classess which do not offer viable dps or tanking (as well as those people who just plain enjoy healing). Unless content is balanced for far lss healing than we are used to some people will be stuck healing even if they would rather be doing something else, and those people are going to come from the class that ofers the least dps/tanking viability.

Edit
Apologies to the OP for taking us off topic this fast.
I do imagine the vast majority of the paladins will be leveling as 41 ret.

Just a quick note:

One of my friends specced prot on PTR and we went and did a ZG. Using whatever miscellaneous mediocre tanking gear he's picked up (he's a full time healadin on live), he main tanked ZG without problems.

Now, when I say without problems, I mean with the exception of him getting silenced on Jek'lik, I really didn't have to worry about my aggro, and I considerably outgeared the rest of the raidgroup (I'm Fang/Pugio with 5 pieces of T3, they're mixed T1/T2 for the most part). Trying to rip aggro, if he got a few seconds start, was pretty much a futile endeavor. Talking with him after the fact doing post-mortem, we pretty much came down to feeling comfortable with a paladin tanking most of the current content pre-Naxx, barring the Emps (we both feel that given no real way to prevent a crushing/UBS combo for a paladin, that encounter just isn't suitable). I actually imagine a paladin could tank 4H just as well as a druid can, at this point, although gear would be an issue to some extent.

Once paladin tanking gets itemized properly and the rest of the changes come in, I expect them to be fairly solid tanks, quite comparable to warriors and druids, superior in some encounters.