I remember the old Seven Cities of Gold on the Commodore 64. That was a lot of fun
Sid Meier did Colonization! back in the early 90's but it stopped when you won your independence from Europe.
What would be fun is to have a map filled with a huge number of provinces covering the entire New World (to include islands). You start out as either a explorer, privateer, colonists (or have units under your command that can do those things). The AI would run the other European Nations and Native nations (and tribes).
And away you go. Add in technological advancement, political events, building/city development. Have it go all the way from 1492 until the 'official' closure of the American West in 1890.
I'd even go as far as having variable victory conditions for countries/tribes you play (e.g., if you are the Sioux, you win if you survive as an independent tribe until the end of the game; if you are the English, you win if you maintain control over x% of North America by 1890, Spain if you control x% of South America by 1890, and so on). You could script the major conflicts to occur if certain conditions are met (French and Indian War, American Revolution, wars of Latin American independence, etc.). If you wanted to simplify technology, just have improvements appear at pre-set times (ironclads in 1862, for example).
It would be a beast to develop, but it would beat any other game out there. If you could make a random map generator, that would give unlimited play value.
That would be massively fun to play.