Commander Bello
Say No 2 Net Validations
There are many ways to befriend the natives.I know some tribes are more aggressive than others, but there's something fundamentally wrong with portraying the natives in general as nothing more than a huge latent menace that has to be eliminated sooner or later. There's precious little that can be done to appease them, and European expansion gradually and inexorably angers them. Who knows, maybe I should actually trade with them instead of just dealing with the King.
1st: Trade
Invest some money into trading goods and trade them. This will give you resources or - in many cases even more valuable - food at low prices. If you can afford it, don't have the natives pay the whole price, but ask for less - and in turn, give them more than what they ask for. This will improve your relationships.
2nd: Missionaries
A mission in native village will make them less annoyed about the spreading of your "culture". As soon as you acquire an "experienced missionary", build a school somewhere and put a student in it. Even if a missionary cannot be trained in the (basic) school, it will preserve the knowledge for later use. Have the missionary working in your city for at least one complete turn to make sure that his knowledge is kept. Then send him out to the native's settlement at which you expect the hightest rate of your culture to be inflicted.
And finally, if all of this does not help, keep in mind that we are in the time of colonization. War actually is a means of politics.
An early war can give you space for some cities to produce bells without going into conflict with the natives anymore.
Actually, war in the context of the game can be an investment into future development. Maybe this is not very "civilized" - but it is effective.