> I doubt we can actually uncover fitness functions that reliably maps to "fun"

You don't have to. Get empirical data and form a proxy evaluator. Usable enough for most evolutionary algorithms. I've done this sort of stuff for very subjective metrics and actually sold something with it.