Surely there is a transform that would convert the "hard" space into the terms of the "easy" space, so that the size of the targets could be compared apples to apples.

But isn't this the same as computing a different measure (i.e. not the counting measure) on the "hard" space? If so, you could normalize this to a probability measure, and then compute its Kullback-Leibler divergence to obtain a measure of information gain.