What is necessary and/or sufficient for polynomials to provide isomorphic quotient rings?

Even assuming $R = k$ is a field (which I will do throughout), there is no really satisfactory simple condition, but there is a name associated to the phenomenon: Tschirnhaus transformations. And we can say a few things about them.

Specifically, if $k$ is a field and $f,g$ are two monic polynomials of the same degree in $k$, which for convenience I will write in different variables $f \in k[X]$ and $g \in k[Y]$, a Tschirnhaus transformation of $f$ into $g$ is an element $u$ of the algebra $k[X]/(f)$ whose minimal polynomial is $g$ (and sometimes a polynomial $U \in k[X]$ representing $u$ is abusively called the Tschirnhaus transformation). Note that the minimal polynomial of $u$ can be algorithmically computed as the resultant in the variable $X$ of $f(X)$ and $Y - U(X)$. A Tschirnhaus transformation of $f$ into $g$ is essentially the same thing as an isomorphism between $k[Y]/(g)$ and $k[X]/(f)$, the isomorphism being represented by $A \mapsto A\circ U$ for $A \in k[Y]$. So we can also give the following criterion: a Tschirnhaus transformation $U$ of $f$ is a polynomial $U \in k[X]$ (or more rigorously, its class mod $f$) such that there exists $V \in k[Y]$ for which $V\circ U \equiv X \pmod{f}$ (the transformation is into the minimal polynomial $g$ of $u$, computed as explained). This $V$ is, obviously, called the inverse (or "converse") Tschirnhaus transformation to $U$.

Now we can reduce to the case where $f$ and $g$ are irreducible, because:

• If $f = f_1 f_2$ where $f_1$ and $f_2$ are monic and relatively prime, then a Tschirnhaus transformation $U$ of $f$ is exactly the same thing as two Tschirnhaus transformations $U_1, U_2$ of $f_1,f_2$ such that the polynomials $g_1,g_2$ that they transform into are relatively prime ($U$ is congruent to $U_i$ mod $f_i$ and transforms $f$ into $g = g_1 g_2$). This follows easily from the Chinese remainder theorem.

• If $f,g$ are monic, then a polynomial $U \in k[X]$ defines a Tschirnhaus transformation of $f^r$ into $g^r$ iff it defines one of $f$ into $g$.

So if we factor $f = \prod f_i^{v_i}$ and $g = \prod g_j^{w_j}$ with the $f_i$ and $g_j$ irreducible, the polynomials $f$ and $g$ are Tschirnhaus-equivalent iff there is a bijection $i \mapsto j=\sigma(i)$ such that $f_i$ is Tschirnhaus-equivalent to $g_j$ and $w_j = v_i$.

Also note the following: if there is a Tschirnhaus transformation $U$ of $f$ into $g$ (monic, of same degree), and if $E$ is a splitting field of $f$ over $k$, then $E$ is also a splitting field of $g$ over $k$. Indeed, $U$ is still a Tschirnhaus transformation of $f$ into $g$ when $f,g$ are viewed as polynomials over $E$, but since $f$ is split, $g$ also has to be split.

So now we can assume $f$ and $g$ irreducible (of the same degree), so that $k(x) := k[X]/(f)$ and $k(y) := k[Y]/(g)$ are fields (the rupture fields of $f$ and $g$). The fact that $f$ and $g$ are Tschirnhaus-equivalent can then be expressed in a slightly simpler equivalent form: $g$ has a root in $k(x)$ (i.e., there is $U$ such that $g \circ U \equiv 0 \pmod{f}$; then $g$ is necessarily the minimal polynomial of the class $u$ of $U$).

Suppose moreover $f$ and $g$ are separable and $k$ has a splitting algorithm (i.e., we can algorithmically compute the factorization of a polynomial $h \in k[T]$ into irreducible factors). Then there is an algorithm for deciding whether $f$ and $g$ are Tschirnhaus-equivalent: indeed, we saw that we can assume $f$ and $g$ irreducible, and that it is then the matter of deciding whether $g$ has a root over $k(x) := k[X]/(f)$; but the latter is solved by factoring $g$ over $k(x)$, and since $f$ is separable, $k(x)$ has a splitting algorithm (see Fried & Jarden, Field Arithmetic, lemma 19.2.2, or Stoltenberg-Hansen & Tucker, "Computable rings and fields" in the Handbook of Computability Theory, theorem 3.2.4).

[Edit: perhaps the following criterion is simpler or more satisfactory: if $f \in k[X]$ and $g \in k[Y]$ are monic of the same degree $d$, separable and irreducible, they are Tschirnhaus-equivalent iff the quotient $k[X,Y]/(f,g) = k(x) \otimes_k k(y)$ by the ideal they both generate, and which is a product of fields, has a factor of degree $d$ over $k$. Indeed, this algebra is $k(x)[Y]/(g)$, a product of extensions of $k(x)$ which has a factor of degree $1$ over $k(x)$ — or equivalently, of degree $d$ over $k$ — iff $g$ has a root in $k(x)$. Now we can apply algorithms of (zero-dimensional) primary decomposition to $(f,g)$ to find whether it is the case.]

[Edit 2: Here is a more detailed algorithm to test whether $f,g$ (monic separable irreducible of same degree $d$) are Tschirnhaus-equivalent, assuming for simplicity that $k$ is infinite. First, we find $\lambda\in k$ such that $x+\lambda y$ is primitive in the sense that the monic generator $h \in k[Z]$ of the ideal $(f,g,Z-X-\lambda Y) \cap k[Z]$ (computed by algebraic elimination of $X$ and $Y$) is of degree $d^2$: since this is the case for all but finitely many $\lambda$ and $k$ is infinite, this can be found. Once this $h$ has been found, factor it over $k$: it has (at least one) factor of degree $d$ iff $f,g$ are Tschirnhaus-equivalent. If $h_0$ is such a factor, compute $(f,g,Z-X-\lambda Y, h_0) \cap k[X,Y]$, again by algebraic elimination, and more precisely, compute a Gröbner basis for the lexicographic order with $X<Y$: this basis will be of the form $f(X), Y-U(X)$ where $U$ is the desired Tschirnhaus transformation.]

As seen above, if $f$ and $g$ are separable, a necessary condition for $f$ and $g$ to be Tschirnhaus-equivalent is that they have the same splitting field in some fixed algebraic closure of $k$. This is not sufficient (even if $f$ and $g$ are irreducible): $X^4 - 2$ and $Y^4 + 2$ over $\mathbb{Q}$ have the same splitting field (namely $\mathbb{Q}(\sqrt{-1},\sqrt[4]{2})$), but they are not Tschirnhaus-equivalent since $\mathbb{Q}[X]/(X^4-2)$ can be embedded in $\mathbb{R}$ so it contains no root of $Y^4 + 2$. However, the criterion can be refined as follows: $f$ and $g$ (monic separable and irreducible of the same degree) are Tschirnhaus-equivalent iff they have the same splitting field $E$ and moreover, if we let $P$ and $Q$ be the subgroups of $G := \mathrm{Gal}(E/k)$ fixing a root of $f$ and $g$ respectively, then $P$ and $Q$ are conjugate in $G$. (This is an easy consequence of the fact that an isomorphism of rupture fields extends to an automorphism of the splitting field.)

All of this is fairly simple, and I'm not sure any of it can really be said to answer the question, but I don't think one can do any better.

$$R[y]/(f(y))\cong R[x]/(g(x))$$ as $R$-algebras iff there exists $\phi,\varphi\in R[t]$ such that $$f(\phi(x))\in (g(x)),\quad g(\varphi(y))\in (f(y)),\quad \phi(\varphi(y))-y\in (f(y)),\ \varphi(\phi(x))-x\in (g(x))$$

The isomorphism is $y\to \phi(x)$ with inverse $x\to \varphi(y)$.

Note that if $R$ is a field, $f$ is irreducible and $\deg(g)=\deg(f)$ then the existence of $\phi$ is sufficient.