Welcome to DDO! It's a lot of fun, and I'd say you're ahead of the curve for looking up a guide
there's quite a few game mechanics to be learned.
Part of the reason there aren't many latest up-to-date guides for Barbarian/Paladin is that they haven't had many build-shifting changes recently. Barbarian got some buffs, but they didn't change how the builds worked, and Paladin is slated for an update in the upcoming future (I think someone said this year?). Two-Handed Fighting is also in need of some buffs, but I'd still recommend it for new players for ease of playstyle.
That said, both are pretty reasonable. Barbarian does more damage, Paladin is a lot tankier and has more utility (mostly heals etc).
Ironically I'd recommend a nearly identical build for either one since you're new, just get a big weapon (Falchion > Greatsword > Greataxe) and go hitting
Paladin or Barbarian 20
Race - any works, but Warforged is hard and ideally you don't want Strength or Constitution penalties.
Alignment - limited by your class, Paladins are LG and Barbarians are non-Lawful (I'd probably go true Neutral).
Barbarian stats:
18 Str (hitting stuff), 16 Con (Rage duration, HP). 10 in Int probably, but that's up to you (Int gives a skill point, Dex +1 AC/Reflex, Wis +1 Will, Cha is... uh... +1 Intimidate?). Level-ups into Strength.
Paladin stats:
16 Str (hitting stuff), 14 Con (HP), 10 Wis (spellcasting), 16 Cha (saves, heals, and Divine Might to Strength). Can level-up Strength for a slight DPS advantage, or Charisma for better utility (and with Divine Might you get half Cha to Str anyway); personally I do Cha.
Skills:
- Jump (required QoL for a melee)
- Intimidate (get enemies off your buddies and focused on you)
- Heal is nice for Paladins
- Swim is fun but totally not required
Feats:
(1) Power Attack (toggle, do more damage always)
(3) Cleave (active AoE attack)
(6) Great Cleave (a second of them)
(9) Improved Critical: Slashing (more damage with slashy stuff)
(12) Two Handed Fighting
(15) Improved THF
(18) Greater THF
(21) Overwhelming Critical (better crits)
(24) free feat (Weapon Focus for +2 Melee Power?)
(26D) Perfect Two-Handed Fighting
(27) Epic Damage Reduction
(28D) Perfect Two-Weapon Fighting (gives Doublestrike)
(29D) Dire Charge
(30L) Scion of Arborea
(30) Blinding Speed
If you're human (with a bonus feat) you can grab the first THF at level 3 and continue as normal (with a free feat at 18) or you can take your free feat at 3 and continue as normal. Your free feats are pretty open, but you might consider grabbing a Dragonmark for a bit of fun/convenience.
Barbarian AP:
Frenzied Berserker is currently considered best, get Blood Tribute early and keep going. Grab cores whenever possible, and Supreme Cleave + Blood Trail is pretty great. I'd fill out the T5 except for Lash Out (which seems weak). I'd also probably take Accelerated Metabolism vs Raging Blows. After FB, you can split between Occult Slayer, Ravager, and your racial tree or focus on one specifically. I really like Arcane Encumbrance (T3 OS) and all the core enhancements are really strong so try to get as many as possible. That said, there's not really wrong choices to be made here. If you're Human, spend at least 3 AP for the first Healamp
Paladin AP:
Early points into Sacred Defender (+3 Lay on Hands, +15 PRR w/Stance, Defender Stance) then into Knight of the Chalice (Cores, Divine Might, MP boost, better Smites) then back to SaD (+20% HP in stance) then to KotC when you get the T5 (take all but Avenging Cleave; Holy Retribution is really nice though) and then back to SaD for Core 4 (to rez), 10% Movespeed, and +6 Strength. Also worth dipping into your racial tree if there's good stuff
but I'd recommend a final split of 41 KotC, 25 SaD (with 14 leftover).
Toggle on your stances, buff up (Divine Might, Rage, etc) and go ham
both classes do pretty well with wading into a pile of enemies and cleaving a bunch. Barbarian has better DPS, but will be a bit more dependent on external healing (bring a hireling, park them and summon for heals) whereas Paladin is super tough and also comes with a bit of healing. Holy Sword and Zeal @Paladin 14/15 also help even the DPS out a bit, but it'll still be a bit behind.
-----
Does that help explain a little of what you're looking for?
-----
If you're looking for a S&B Paladin, I'd highly recommend
Strintom's Vanguard Paladin.