I'm also with the camp of doubters:

One of the nice aspects of R;TW are the city sieges. But to have to do 4 or 5 city sieges to control a province is annoying. Raid tactics would just play a too important role, and the game could inherit the silly sea battle thing from M;TW (one ship blockading and moving around each turn so you can't catch it unless you make faster ships).

Founding new cities may sound nice and plays ok in Civilisation, but here alot would have to be drastically altered to the game I think. Because 2 cities next to eachother should not be allowed (spamming one island full of cities is just unrealistic), the game needs now to calculate the worth of terrain so that the income of the town isn't some random number. Probably have to make up some trade goods as well etc etc.
While I can imagine that there might be events which create cities (thus generated by the game itself, on places predetermined), so that everything (including income trade goods etc) are predetermined that it wouldn't be seen as odd or out of place.

I like the flexible borders and conquering half a land-remarks, but it is really hard to implement I think: How much land would you conquer if you build a town in the middle of a land, where at one of the edges, there are 2 more towns? or 3? Would an extra town make difference? How much? WHo holds the title for the province? can you split up the province so that you get more governers?
Basically the only way I see this as being possible is if you are cutting the provinces up more, into miniprovinces (if you want to). Although there might be people who like that, I for one think the map will be big enough for some quality campaigns, more (mini-)provinces would just make the game even longer.