[HoneyBadger]

I'd like an auto-generated cave system feature, so that you could search for caves in a province and may find one-might just find a slab of granite-but the cave system itself would be random.

You could still have user-generated cave systems, but this would allow extra random cave provinces that noone would know about until you found them. You could even find extra random caves in provinces that already are-or connect to-established user-created cave systems. Some would be dry land-based caves, while others would be full of water. You might even have some filled with lava.