Ok, that's very interesting. I think I will not get above Governor for now, as my game was.. pretty smooth, but not too easy on this level of difficulty (I'm very hardcore fan of Colonization "1" and only few days ago I found this mod, since so many questions

). This is great that AI doesn't use cheats. In Col1 I believe most of AI's power came from free city improvements and getting 20 tools/trade goods/muskets in every new colony.
It depends on the specific Native Leader.
That's something that I'm going to watch for from now on

it must have been that difference.
After checking out :
Oconostota - these Indians just ran away and left me their villages (I had -2 relations +2 base +3 years of peace -7 your ways of life)
Sioux - these "bomb rushed me" with 20 troops entering my borders from every direction and 2 of my small 1-pop towns going down the first turn of war

I loved it, despite harsh consequences. (I also had a little bit worse relations with them, at -4)
Now I think it makes sense. Sioux are more war-like and first ones look "gentle" (tho I don't know their history). Still - I think even gentle Indian tribes should fight player if he is just trying to expel them away. I miss col1 Indians that would attack you from time to time even at most positive relations

They were not "country" they felt more like collection of people (even though most of them like you, some don't and will attack you)
But I understnad this is impossible in how civilization IV engine works... Or maybe - there could be some "hostile natives" spawning in normal native villages, when player takes their city down with his culture? These hostile natives have "hidden nationality" flag, so they could just walk and attack player.