Fighters: Fighters have changed very little from OD&D. They're still the best class in battle, able to use their strength more effectively and wield all weapons and armour. As before, a 9th level fighter can establish his own stronghold and collect taxes. In OD&D the figure was set at 10gp per inhabitant per year. In AD&D, it's 7sp per month, which comes to 84sp per year - equivalent to about 4 gp per year. Looks like AD&D fighters are taking a pay cut. Probably the most significant change for Fighters is the jump from using a d8 for hit points to a d10. There's honestly not a lot else to say. It's the baseline class, and Gary didn't see the need to change them.
Paladins: The first thing to be noted here is that it's a lot harder to become a paladin than it was in OD&D. All you needed there (assuming you were Lawful in alignment) was a Charisma of 17. In AD&D, not only do you need the 17 Charisma, but you also need a Strength of 12, an Intelligence of 9, a Wisdom of 13 and a Constitution of 9. I looked at some other guy's math, and if you roll your stats using 3d6 in order there's a 1-in-1000 chance that you'll get a paladin. Good luck with that!
The new alignment system has, of course, necessitated a change to the restrictions on paladins. In OD&D they had to be Lawful, and now they must be Lawful Good. (This may have been introduced with the five-point alignment system from The Strategic Review, but I can't really remember). A paladin who acts against their alignment will suffer a penalty, but an Evil act is punished more strictly than a Chaotic one. If a paladin commits a Chaotic act, he can atone by doing penance as prescribed by a high-level cleric. An evil act will cause the paladin to lose all their abilities irrevocably, with no takesies backsies. (In OD&D, a Chaotic act was treated as an Evil one is here.)
As far as special abilities go, their +2 to all saving throws remains, as does their immunity to all diseases and their ability to detect evil at will. Their "lay on hands" ability works exactly as it did in OD&D, but their ability to cure disease in others has been a bit nerfed: before it could be used daily, but now it can only be used once per week (with extra uses at higher levels).
In OD&D, 8th level paladins gained the nebulous ability to "dispel evil" simply by ordering it hence. That's gone in AD&D, but it's been replaced by a continuous aura of protection from evil, which now that I look at it is pretty badass. It's an ability I usually forget about, but the fact that it's always on makes this one of the paladin's most potent.
The paladin's warhorse is now explicitly said to appear as if by magic. It's otherwise the same, except that in OD&D you could interpret the rules as saying that the horse has all the same abilities as its paladin master. There's no such ambiguous wording here, unfortunately.
Unless I've missed something in the OD&D rulebooks, I believe that this is the first time that higher-level paladins get the abilities to turn undead and cast cleric spells (although perhaps the "dispel" ability I mentioned above was meant to represent turning).
Paladins are still restricted in the number of magic items they can own, and the amount of treasure they can amass. The numbers here are much the same as they were in OD&D.
Paladins weren't given their own level titles in OD&D, so here are the newly created ones for AD&D:
Level 1 - Gallant
Level 2 - Keeper
Level 3 - Protector
Level 4 - Defender
Level 5 - Warder
Level 6 - Guardian
Level 7 - Chevalier
Level 8 - Justiciar
Level 9+ - Paladin