A server can easily add an extra random wait to all unauthorized responses, making such attacks almost infeasible (at least for web-app case).
But another possible way is to add a deterministic amount of additional wait time (instead of random), i.e., "lie" about computation time of all inputs consistently. If designed properly, this won't leak any signal (assuming the strategy on how to "lie" is chosen randomly itself and shuffled often, so attacker doesn't learn it).
Strategy of waiting for maximum time across all possible requests (as mentioned in your post) is sort of a special case of this, where one (deterministically) add a wait time of W - C (where W = Worst case time across all inputs, and C = actual time taken for this input). But we can use a less aggressive approach to hide the actual computation time as well.