There is an automatic, fairly significant increase related to distance. A province which is 10 squares away from your city is going to be a good bit harder than one which is only 9 squares away. There is also a smaller increase every time you scout a province. Every time you scout a province, the next one is slightly more expensive. If you do this enough it can cause provinces to increase in difficulty, even if the distance from your city remains the same.