2) The paladin has trample as a feat. Does he actually have to ride the horse to get it to trample, or can he just tell it to, as it is fairly smart and can follow commands.
Yes, the horse can grapple just fine if it is willing to suck up the AoO.
Keep in mind that most similar size and Str creatures have Improved Grab, Rake, Constrict, or Rend, so the horse implicitly has an big grapple penalty: It gets no bonus.
But the point is to not have the mount grapple equal opponents. Tell it to go after the halfling, or the caster, or someone with abysmal grapple checks.
A special mount gets new feats when their HD advances to appropriate number (6,9 ...). So, you can let it take Improved Unarmed Strike and then Improved Grapple.
This came up when my paladin was dueling a monk....with improved grapple the monk had me cold everytime, so I wanted to see if my horse could come in and even the odds a bit.