I think the best way to implement a colonial era is to tie it in to the exploration tree which needs a bit of tweaking to make it competitive with Rationalism.
The problem now is that Rationalism is the best of the later era policy trees and most players need to take at least some points in rationalism to keep up on science. And you don't have a lot of time to fill out a whole new tree just for naval expansion/conquest in the mid-game before ideologies kick in.
I think the exploration tree could function for both peaceful naval trading civs and for aggressive colonial empires. Perhaps something like this would work. So you can pick either the aggressive expansion policies or the passive economic policies. So the tree now benefits 2 styles of naval expansion. The finisher is a bit more boosted to put the exploration back into exploration
making archaeology a bit better with fossil sites as well.
Exploration Tree
Opener: +1 movement and sight for all naval and embarked units. Unlocks building the louvre.
Maritime Infrastructure: All coastal cities gain +3 production
Colonialism: Receive a free Conquistador and a free Caravel at your capital (or nearest coastal city). Cities settled on new landmasses gain +1 population, +1 happiness, + 5 defense and +50HP (requires Maritime Infrastructure).
Imperialism: Gain +20% productivity toward Renaissance era land and naval military units (requires Colonialism).
Naval Tradition: +1 happiness for every lighthouse, harbor or seaport. A great Admiral appears. Great Admirals gain +2 movement. Great Admirals are earned 25% faster (requires Maritime Infrastructure).
Treasure Fleets: Receive 1 additional trade route. A free cargo ship appears in the capital (or nearest coastal city). Gain +2 happiness and +3 gold from improved luxuries on foreign landmasses (Requires Naval Tradition).
Adopting all policies in exploration grants 2 free archaeologists and allows you to see hidden antiquity and fossil sites (give science benefit to museums or produces a fossil dig-site providing science to city). Allows you to purchase Great Admirals with faith from the industrial era.