One thing I am wondering about, should we make all provinces other than the initial settlements empty? The downside to that is that the empty provinces provide no income or benefits other than territory but the spirit of pure settlement is maintained.
The other approach would be to maintain a number of slave pops (perhaps keeping them as mechanoids) so that there is some benefit to expansion. The problem is that this loses the spirit of settlement.
One approach (given the 500 year time span) would be to dramatically increase population growth via faction benefits or inventions. Similar to the Suez Canal event, players might get a Cloning Vats event giving them the option of spending massive funds and goods for a significant population boost. This might be simulated as well by providing abnormally high livability in the initial bases.
How can one make a hidden province? I don't know if Victoria supports Terra Incognita.