Kolgomorov complexity seems like the obviously correct measure, though AIUI it's only defined relative to some fixed Turing machine.

I have an idea of doing a PageRank-style weighting of Turing machines, based on how simple/complex simulating one under another is. That would align with my intuition that most basic universal Turing machines are equally valid, but one that has (say) a short instruction that outputs one particular long sequence of symbols is probably not a valid machine to use.