OP EDIT: Wolfram Technical Support got back to me and confirmed this is a bug. But the Answers below provided good workarounds.
I have two polynomials respectively in {z,c} and in {r,z,c}. I'd like to eliminate z and get a tidy expression in {r,c}. For some reason, Eliminate[] never completes this simple task, while Solve[] quickly succeeds at the harder task of finding r as a function of c. But the Solve[] result is messy, so I'd like to know how to get just Eliminate[] to work.
Edit: I believe the solution should be a fairly simply polynomial in {r,c}.
The first three lines of code just generate and display my two polynomials.
w[n_, z_, c_] := If[n > 0, w[n - 1, z, c]^2 + c, z];
p1 = PolynomialQuotient[w[4, z, c] - z, w[2, z, c] - z, z]
p2 = 2^4; Do[p2 = p2*w[i, z, c], {i, 0, 3}]; p2
Solve[{p1 == 0, p2 == r}, r, {z}]
Eliminate[{p1 == 0, p2 == r}, {z}]