>The ratio of two polynomials of identical complexity will have twice the number of degrees of freedom as each of its polynomials
I wrote with "Pade approximants would be more accurate with less work." for a reason.
If they have identical complexity they cannot have twice the degrees of freedom. You're confusing ideas here.
First, there are a lot of ways to evaluate Pade than a naive compute two polynomials and then divide them. There's quite a large literature on evaluation methods, just as there are for polynomails (and the naive polynomial evaluation method is generally terrible - at least consider Horner's method).
Second, the Chebyshev poly of deg d can simply be the Pade poly P(n) / 1 with P(n) of degree d. Thus Checbyshev is a special case of Pade at the same cost. Thus it's a smaller class, in the pure mathematical sense that one space of functions is a strict subset of the other.
So if you want to check all approximations of fixed computational complexity, vary the top and bottom degrees appropriately to check a strictly larger space of approximants for fixed computational cost. You'll usually find that Pade, for the same computational cost, makes a better approximant. It's simply richer.
What's more, once you have computed the various powers of x, you can reuse them (unless you're using Horner's method or similar, which is generally better).
If you're really looking for minmal cost computation, there is another entire literature on decomposition of functions to minimal operations, and finding the optimal one is NP-complete (but completely doable for these low order approximations). Knuth TAOCP has an intro to the lit under (if I recall) "addition chains" for evaluating polynomials. There is parallel theory for Pade.
Thus Pade is a strictly better method. It completely encompasses Chebyshev, and since I've used it a lot, I have found it always better, for the same computational work.
It simply let's you optimize over a larger class of approximants.