I agree with the first point, and I don’t have solid solutions to this. There’s also the fact that some games are easier to optimize than others (name a number game I described at the end vs. chess), and this complexity is impossible to capture while staying computation-agnostic. Maybe one can use the length of the shortest proof that taking action a leads to utility u(a) to account for these issues..
The second point is more controversial, my intuition is that first agent is an equally good optimizer, even if it did better in terms of payoffs. Also, at least in the setting of deterministic games, utility functions are arbitrary up to encoding the same preference orderings (once randomness is introduced this stops being true)
Thanks for the pointers, I should have done more research before writing this up. After a quick glance my initial impression is that there still isn’t a good solution (even an uncomputable one) to the problems such as the one I describe at the end, or the one AlexMennen mentions.