There are 2 components to the cost of exploring: the cost per explorer sent and the number of explorers required to find one acre.
This is based on your adjusted acres (Total Acres + Explored Acres) Explored acres even count dispite that your lost them to and attack earlier. You may notice that this basically means explored acres count double, acres gained through attack count once.
0-2000 adjusted acres it costs 300gc to send 1 recruit exploring
Over 2000 adjusted acres it starts a 301gc and grows to over 2000gc per unit sent at 10,000 adjusted acres.
1st Province only explores, never attacks. (explorer)
2nd Province only atacks, never explores. (attacker)
They will have the same cost to explore (per unit) when the explorer is at 2150 acres and the attacker is at 4000 acres.
adjusted acres for explorer = (2150 ttl + 1850 explored) = 4000
adjusted acres for attacker = (4000 ttl + 0 explored) = 4000
This is based on your current acres, not adjusted acres.
Starts at 1.2 recruits to find an acre (at 300 acres) and grows to about 30 recruits to find an acre (at 5000 acres).
This cost is the same for everybody no matter how they got their acres.
It is always cheaper to explore early than later. But this will make exploring later nearly impossible if you do it too excessively...
If 2 provinces are sitting at 5000 acres each, the one who explored the least has a massive advantage.