The Houyhnhnms immediately identify Gulliver as some variation of a breed from the Yahoos, because Gulliver shows up in the land of the houyhnhnms wearing clothes. In fact, Gulliver's first encounter with the yahoos is not very pleasant; they act so savagely and are so hairy that he does not recognize them as being human at all. They all surround him and begin to pelt him with feces. Gulliver's clothing, however, distinguishes him as being something more than just a regular yahoo, and a kindly houyhnhnm interceded on his behalf, rescuing him from the yahoo mob.
Although the Houyhnhnms recognize Gulliver as being a far superior version of a yahoo, they also perceive him as a possible threat and decide in their assembly that he should not be allowed to stay in their land.
To the Houyhnhnms Gulliver is different from the Yahoos not only because of his clothes but because he is capable of clear speech and he is less animalike and lewd than his hairy counterparts.