Pressburg in Austria has a lot of Native companions.Sini. said:Found the Nizar companion from Native Warband in Gießen tavern. I recruited him and he is using all Native equipment, nomad boots etc...
Also, I forgot in which location but it was possible to buy one of the heavy warhorses from Native.
EDIT: Also found Bunduk at Milano.