Added (7/19/2010): The answers below, particularly Ryan Williams' excellent survey of the dependence of the time complexity of various problems on their encoding, get at the motivation to my question but not at my question itself. In particular, it's clear that every problem may be re-encoded to allow (say) $O(\log n)$ time complexity, by padding. My question is whether there's a reasonable way to measure this dependence.
For example, say the decision problem for $L_1$ is reducible to the decision problem for $L_2$, and vice versa, so that $L_1$ and $L_2$ in some sense represent the same problem. Is there a way to formalize this last statement (about "representing the same problem")? I am imagining, for example, a measure $C_i$ of the complexity of a language so that if $T_i$ is the time complexity of the language, and $L_1$ and $L_2$ are, say, easily reducible to one another, then $T_1/C_1\sim T_2/C_2$. (Of course $C_i=T_i$ works, but ideally $C_i$ would be somehow a property of the language, rather than the decision problem.) This is unfortunately becoming quite speculative, so again, related references would be a great answer.
