Heck, as a paladin you'd even get smite evil (OK, so there'd be no bonus to hit but you'd add one point of damage/level) a mount (eventually), and Aura of Courage too.
OTOH, those would all come with experience penalties unless your DM changed the paladin multiclassing rules or you play in FR and follow one of the deities who allows paladin multiclassing with fighter). After all, neither paladin nor fighter are favored classes for a half-orc so you'd have to keep them within one level of each other. The difficulty of this is that you could start as a fighter, get two fighter levels, and then get three paladin levels but then you'd have to switch back to fighter or start taking xp penalties. And once you've switched to fighter, you wouldn't be able to go back to paladin so after you hit 4th level fighter, you wouldn't be able to avoid xp penalties except by taking prestige classes. (Any further core classes you took would start at level 1 and consequently incurr serious xp penalties until you hit level 3 (and after you exceed level 4) in that class).