I'm keeping Cleave though, since the DM likes to cluster mobs in hallways and I have gotten some good use out of it.
Sorry for the double post, but light armor + Liont Totem Babrarian (just the first level ACF) from Complete Cheatyface is a much, MUCH better option than blowing a feat for Cleave. Unless you plan to go Frenzied Berserker, which opens up a whole new can of whoopass... and complexity.
"Today's headlines and history's judgment are rarely the same. If you are too attentive to the former, you will most certainly not do the hard work of securing the latter." -Condoleezza Rice
"My fellow Americans... I've just signed legislation that will outlaw Russia forever. Bombing begins in five minutes." - Ronald Reagan
This user has been brought to you by the letters "O-R-C" and the numbers "2, 3, 4, and 6"
Resident Pithed-Off Dragon Buttler of the House of Trolls
Hmm. I'm not familiar with class variants, but the DM obviously doesn't mind them since we have a CG paladin with us. What makes the Lion Totem better than other choices?
Lion Totem barbarians give up their fast movement ability in exchange for Pounce. Fast Movement is a nice ability, but one that's trivially easy to take up with equipment over time, and it doesn't really help barbarians much - if you move more than 5' (i.e. if you take advantage of Fast Movement), you can only make one attack this round, and barbarians really benefit from having access to multiple attacks. Meanwhile, Pounce is "you can take a full attack at the end of a charge" - so if you're level 7, you can swing twice at the end of a charge attack, which involves moving double your speed anyway. And I did just mention that barbarians really benefit from having access to multiple attacks, didn't I?
What makes it better than the other totems? Pounce is one of the single best melee abilities in the game, and it's traditionally quite hard to get ahold of, and here Complete Cheeseball hands it out at level 1 to the class which probably benefits the most from it.
In order to make sure that the limits on charge mobility don't hinder you, you might consider the charge-related skill tricks in Complete Scoundrel as well (Twisted Charge and Nimble Charge). They're cheap, and barbarians get skill points to spare.
As a minor aside, the reason why Draco is, quite correctly I think, pointing out that barbarian isn't really conductive to a mobile heavy hitter is the same reason why we're recommending Pounce. Normally, you can't move and full attack, and it's full attacks (and the ability to hit multiple times) that normal melee characters really rely on in order to dish out damage. There are, broadly speaking, three ways around this: Extra actions (hard to get on a melee character, but the swift hunter handbook goes into this a lot), Pounce (discussed here), and switching away from full attacks. To switch away from full attacks but keep your damage up, one usually switches roles altogether, moving into what we call "AoO Tanking" (basically, responding to everything your opponents do with an Attack of Opportunity), but you can also just pick up a martial adept. The strike abilities available to a warblade, for instance, can still feel very barbarian-esque without costing you much in the way of damage. (Warblades work amazingly well as many different warrior archetypes, from the savage but cunning barbarian to the clever and swift swashbuckler to the noble leadership of the samurai.) The strikes are more mobile than charge attacks because most strikes take only a standard action to use, so you can still move before or after the strike - and this movement isn't subject to the same restrictions that charge attacks are.
The warblade - and martial adepts in general - solved a lot of problems with D&D melee which had formerly required a lot of finesse and familiarity with the rules to get around. (For instance, until the book came out, you'd have to be an absolute master of the attack of opportunity rules and/or extremely comfortable playing with Power Attack numbers just to keep up with monster HP.) If you need free online material only, there's quite a bit of the basics of the warblade and the book it's from available here and here.
These are NOT all my creations! The lead authors are identified as follows: [TS] Tempest Stormwind, [AR] Andarious Rosethorn, [RT] Radical Taoist, [SN] Sionnis, [DH] DisposableHero_, [SH] Seishi.
[TS] The Pinball Brothers: Large And In Charge (Melee, Lockdown, Charge, Juggling) [TS] Ashardalon Reborn: I Will Swallow Your Soul (Melee, Fear, Negative Levels, AoE, Theme) [AR] "A"-Game Paladin: Play That Funky Music, Knight Boy! (Team Support, Melee, Theme, Single-Class) [RT] Uncanny Trapsmith: Get in, make it look like an accident, get out. (Skillmonkey, Stealth/Scout/Infiltration, Unorthodox Methods, Theme) [AR] Wizsassin: *Everything* is permitted. (Spellcaster, Support, Sneak Attack, Utility) [TS] Phantom Rush: General Gish Gouda. (Gish, Theme, Setting-Specific(Eberron), Early-Entry PrC) [TS] Storm Knight: Another kind of gish. (Melee/"Gish", Theme, Setting-Specific(Eberron), Unorthodox Methods) [TS] Inevitable Nightmare: The weapon you only have to fire once. (Melee, "Unorthodox" Methods (no charging), Reliability) [AR] Captain Constitution: The number one threat to America. (Melee, TOUGHTOUGHTOUGH, Defense, Theme) [AR] Nuker: I casts the spells that makes the peoples fall down! (Spellcaster, damage, blasting, damage) [TS] Dread Lord of the Dead: Let the Reaping Begin! (NPC-only, Variable (combat/casting/leadership), Iconic Villain, Theme) [AR] Heavy Crusader: No Rest. No Mercy. No Matter What. (Melee, Damage (No charging), Variable, Theme). [TS] Gun Fu: It's bullet time (Ranged, THEORETICAL, Twin weapons, Theme) [RT] Face First: We should talk. (Psionic, social, mind-control, info-management) [SN] Chaingun Porcupine: Never Enuff Dakka. (Ranged, Skirmishing, Spike Damage, Incarnum) [RT] Always On Edge: The Mortal Draw deals death. (Melee, Generalist, Dungeoneering, Stunt) [AR] Feral Druid: Real feral taste. Zero druid calories. (Melee, offense, damage, murder) [RT] Rusty!: Man's Best Friend (Sentry, Support, Backup, Rearguard) [RT] The T3 (Tashalatora Triple Threat): My Kung Fu is More Powerful (Hybrid, Flex-Function, Melee, Caster) [RT] The #1 Snoipah: Boom. 'Eadshot. (Caster, Theme, Spike, Trapscout) [AR] Dreamblade: Rest in Pieces. (Melee, Damage, Single-Class, Combo/Momentum) [AR] Evasion Tank: “When fighting angry blind men, is best to stay out of the way.” (Melee, Tank, Unorthodox Methods (attack negation), Theme) [DH] Psycarnum Warrior: ↑↑↓↓←→←→BA Start (Melee, Tank, Psionics, Incarnum, 1337 h4x) [AR] Heavy Weapons Elf: WHO TOUCHED MY BOW? (Ranged, Cohort, Damage, Unorthodox Methods (ranged ToB)) [RT] Gnowhere Gnome: A little man who wasn't there (Caster, Stealth, Single-Class, Elusive) [AR] Uberflank: I got your back. (Melee, support, stunt, teamwork) [TS] Flip the Bird: Everyday I'm shuffling (Ranged, harrier, unorthodox methods (ranged ToB / off-turn movement), support) [DH] Eat Sleep Gank: Real Ultimate Power (Stealth, Assassination, Spike, Magic Versatility) [AR] Slash and Burn: Mind, Body, Blade, Flame / Aspects of a greater whole / which delivers death. (Melee, Theme (flex-style), Damage, Stunt) [RT] Edge of the Light: Cut, Fade to Black (Melee, Defense/Offense, Momentum, Tactical) [RT] Quiet Murder: Cut throats, not corners. (Melee, Stealth, Harrier, Tactical) [TS] Wand Overdrive: Say Hello to my little friends. (Caster, support/artillery/variable, wand specialist) [RT] God Hand: What did the five fingers say to the face? (Melee/Gish, Unarmed, SAD, Theme) [AR] Zero Buff Time Gish: Try to keep up! (Gish, Speed, Movement, Opportunity) [TS] Robo Tackle: I Am Iron Man. (Melee, setting-specific (Eberron), positioning, theme, stunt)