I always preferred the Europa Universalis tiles stile for the added strategic depth it provides. I can only imagine how ludicrously hard it would be to procedurally generate, but at the same time I can't help but think that it should be possible. I know they did something procedural in EU IV with the random new world DLC. Squares and hexagons are the only two shapes that allow to cut a sphere into regular bits. However, it's always looked artificial. Imagine a world generated with some procedural seed that creates a bunch of irregular tiles and then a logic that adds geographic features in a coherent manner across the irregular tiles, I think it would create much more natural feeling worlds, more depth and certainly more unpredictability.