In your induction you start by "Consider a set of n+1 horse" then conclude "By the inductive hypothesis, all of the n remaining horses are the same color".

You did the induction in the wrong direction.

"We can agree to disagree" is not a valid mathematical in my opinion. At least one of us is wrong (and maybe we are both wrong).