Would it be possible to have tribal villages highlighted on the map (maybe using a coloured ring similar to the suggested city sites) that can be toggled on and off? It could be useful when you pop a map from a hut and have to search around for the location of tribal huts.
Something that might be easier would be to use the same effect as when new resources are discovered inside your borders due to acquiring its revealing technology or when a mine you are working suddenly discovers a new resource.
* An on-screen message in the event log: "You have spotted a Tribal Village"
* A sound
* A marker on the tile (same as resource flags) for a few seconds
You could always CTRL + TAB to open the event log and click the events that have occurred to jump to that tile location, same as for all tile-specific events.