I think that when you settles/colonizes a "new world" (places nobody of your opponents have been before you), the natives should be angry on you, and start to figth for their land! Just think of the native americans and how they fought for their land. I don't mean that they must be a ovn civ, maybe theire camps could be a tile improvement.
And just think: after a long and fatiguing journey, Columbus and his settlers stays on american ground. They founds New York. In the beginning, it's all right, but as more and more people comes and new cities are founded, the natives, led of Geronimo, starts to fight....
------------------
Who am I? What am I? do we need Civ? YES!!
