Well, first of all even natives have their own "personality".
Second, I am confused by the description of your army. You're speaking about one military unit, but mention two redcoats (I guess, you're playing the English and are having two Veterans?)
Native troops being gifted to you? I assume you are talking about Converted Natives? These aren't troops, these are just what the term describes.
You may get Native Mercenaries (good for fighting in woods) under certain conditions, but you would have to pay for them. They won't be gifted to you.
To the best of my knowledge, the AI counts your active military. This means the AI counts which units are in a military profession (= militia, dragoon, cuirassier). And of course cannons are counted, too.
If you have built a mission in one of the natives' villages and it produces a converted native, this does not count against your reputation.
Personally, I prefer constant trading about gifting gold, so I don't have that much experience with the latter. For trading, obviously trading goods are good, as are tools. Furthermore, the natives will buy finished goods like coats, cigars and so on, but no raw materials (fur, tobacco...)
Trading weapons or horses will give you the highest prices, but they may use it against you later on. For each native village there is a symbol indicating the most preferred good of that particular village (unfortunately, in most cases this will be weapons). Trading rum will make them a bit happy, too.
As soon as you have more than 1000 gold and are still at decent terms with your monarch you may buy troops for half of the normal price from him (note that prices for troops will increase by doing so and his attitude towards you will decrease due to you building up your army)
Sometimes it may be more fruitful to wait with founding the next settlement and to build up your army first or to improve the current fortifications.
As long as your military is weak, you have to do almost anything to keep the natives at good terms. As you already observed, even a protected settlement may get lost if attacked by too many of them.
This game is very much about making the right decisions at the right time - and there is a learning curve which decision to be made when.