Not directly tied with the resource discovery, but I've always felt that a 'randomized resources' mode would be good. The player knows what places will have useful resources for late-game, but the player doesn't; so we know that eg conquering Arabia gets you a lot of oil late game, or that Southeast Asia is good for rubber, even though in 1836 no one would have planned for that.
I think it would be good if there was a game rule to randomize resources so you're not guaranteed a quantity or location of oil, which would allow a lot more variety in economic gameplay.
