At L1, Two Weapon fighting (TWF) is more optimized. At level 5 the preference switches to Great Weapon Fighting (GWF).
Let's look at why. We're only going to go with a brief snapshot here of L1 and L20. I'm going to assume that Str is 16 at L1 and 20 at L20. Our TWF will wield dual Scimitars (or short swords), and our GWF will wield the Maul or Great Sword.
We'll use the Ogre from the starter as our jousting dummy at L1 (AC 11) and the Nothic (AC 15) at L20 (the Ogre is a near auto hit and thus relatively uninteresting for this particular comparison). The hit chance for our L1 bout is 75%, and the hit chance for our L20 bout is 80%. When a better study of monsters is available to me, I'll update our hit chances here.
To explain the concepts here the TWF gets to add their stat bonus to their bonus action attack, whereas our GWF gets to reroll any 1s and 2s on their first pass of die rolls. We'll be using the following formula for the average die for the GWF:
\$ \text{Avg}(2\text{d}6) = 2\left( \frac2 6 * 3.5 + \frac4 6 * 4.5 = \frac{25} 6 \right) = 8.33 \$
To calculate crits in 5e, you simply multiple the dice rolled by the crit chance. Since nothing is maxed, there is no need to subtract the crit term from the main roll in this edition.
L1 AC 11:
\$ \text{GWF}: 2\text{d}6 + 3 = 11.33 * .75 + .05*8.33 = 8.914 \text{ DPR} \\
\text{TWF}: 2*(1\text{d}6+ 3) = 2*(6.5*.75 + .05*3.5) = 10.1 \text{ DPR} \$
As you can see, at L1, the TWF has an edge of about 1 DPR. Let's look at L20. At L20, our stats go to 20, the fighter makes 4 attacks per round plus the TWF gets his bonus action and the crit range is 18-20 or 15%. Our attack bonus is +11 and our hit chance is 80%
L20 AC 15:
\$ \text{GWF}: 4*(2\text{d}6+5) = 4*(13.33 * .8 + .15 * 8.33) = 47.65 \\
\text{TWF}: 5*(1\text{d}6+5) = 5*(8.5 * .8 + .15 * 3.5) = 36.63 \$
At this point the TWF is heavily outclassed by the GWF. It's not even really close. It becomes a bit closer when the hit chance is lower. But, ultimately, the problem is that the TWF only ever gets that single bonus action attack, and it's not going to be enough to compete with the GWF's big single attacks.
I'll try to get the simpler issues done first - and the simplest one is Great Weapon Fighting. You should not take this. If you're using a spear, it is strictly inferior to the Duelling Fighting Style. See my answer here for the analysis. It's especially true for you because you want to tank, and for a quick and easy boost to your tankiness it's hard to go past a shield.
The next issue is how many levels of Paladin to take. This one gets a lot more complicated, but I'll start with the basics. When multiclassing in 5e, you want to take either 1 level or a number of levels that is a multiple of 4. This way, you don't lose any of the vitally important ability score increases.
The next thing to consider is what you actually want to get out of your Paladin levels, and what each number has to offer you. You also need to consider what Bard features you're missing out on by taking Paladin levels, but you've already got almost all the Bard features - from here on out your existing abilities mostly just get more powerful, rather than you gaining new things.
Paladin level 1: Gives basically nothing. You get the multiclassing proficiencies, Divine Sense, and Lay on Hands. Not a useful number.
Paladin level 4: Fighting Style, Divine Smite, Divine Health, and Channel Divinity. (And 1st-level Paladin spells, for what that's worth.) This is pretty good - a lot of the Paladin's core features for a minimal investment. If you're taking 4 levels, I'd recommend the Oath of Devotion, since (I think) it has the best Channel Divinity options.
Paladin level 8: All of the above, plus Extra Attack, Aura of Protection, and either Aura of Devotion or Aura of Warding. (Technically you could take Relentless Avenger, but it's not that great, especially for what you're trying to do.) Also 2nd-level Paladin spells, which is cool because one of them can be Find Steed, which is basically a class feature masquerading as a spell. This is a good place to finish taking Paladin levels because the next really good feature is at level 15. If you're going this far, the Oath of the Ancients starts looking as good as the Oath of Devotion, because Aura of Warding is so powerful.
I'd definitely recommend either 4 or 8 levels of Paladin if you're going to do this - 1 just seems like a waste of time. As for what order to take levels in, I'd actually suggest waiting till you've got your next ability score increase to do this, because doing it without War Caster might be a little awkward. Obviously, if you want to get better in melee sooner rather than later, you should start taking Paladin levels sooner rather than later, and you can work around the problems with casting your Bard spells with your hands full, it's just tricky.
Best Answer
None of the Oaths really do more damage than the others as such. The only Oath feature that directly impacts your damage is the Oath of Devotion's level 20 ability, Holy Nimbus - it deals 10 radiant damage to any enemies within 60 feet of you. So, to answer your question directly, Oath of Devotion does the most damage.
This is, obviously, a fairly ingenuous answer. The real answer is that you can't look purely for damage.
For example, both the Devotion and Vengeance Oaths have features that increase the accuracy of your attacks, which in the long-term, will increase your damage.
On the other hand, the Oath of the Ancients has an ability that makes you and your allies much tankier and harder to kill. How does that boost damage? Well, you can't deal damage if you're dead, so anything that keeps you alive is also indirectly boosting your damage.
Then there's things like spells. The Oath of Vengeance gives you access to hunter's mark, which potentially lets you add 1d6 damage to every attack you make. But in practice, it's not quite so simple - it requires concentration, and you also have to move it around to make sure it's on the enemy you're attacking. And, obviously, it requires you to make a lot of attacks to maximize the damage it gives.
As a counterexample, the Oath of the Crown gives access to spirit guardians, which deals damage to enemies who come near you - under the right circumstances, this will vastly outdamage hunter's mark. But in the wrong circumstances, it might be completely useless.
So, in the end, there's no easy answer - you'll have to look at all the Oaths and determine which one you think will work best for you.