I personally found the solution to the Native Americans is to do nothing but autocalc them to death until I start rocking up to their territories with at least half a dozen units of howitzers with explosive shells. They never do quite as well in the autocalc, and even worse in a hell of fire and shrapnel. Cavalry love howitzers, one good hit with the boom-boom and they all politely die for me.