Isomorphism of finite dimensional polynomial algebras over finite fields
As you mentioned, you can factor $f_1$ and $f_2$ in polynomial time.  Consider the multiset $D_1$ of degrees of the factors of $f_1$, and the multiset $D_2$ of degrees of the factors of $f_2$.  If $D_1 \ne D_2$, they are not isomorphic.  If $D_1 = D_2$, they are isomorphic.  That takes care of determining whether they are isomorphic.

Computing an isomorphism explicitly is harder.  Let me focus first on the case where $f_1,f_2$ are squarefree, for ease of exposition.  Note that if $f = g_1 \times \cdots \times g_m$, then we have a sort of Chinese remainder theorem:

$$\mathbb{F}_q[x]/\langle f\rangle \cong \mathbb{F}_q[x]/\langle g_1 \rangle \times \dots \times \mathbb{F}_q[x]/\langle g_m \rangle.$$

Consequently, by matching factors of same degree, you can reduce the problem to the case where $f_1,f_2$ are irreducible and $\deg f_1 = \deg f_2$ (in the squarefree case).  Then both fields are isomorphic to $\mathbb{F}_{q^n}$, where $n= \deg f_1$. 

Finding an isomorphism explicitly (if $f_1 \ne f_2$ and $\deg f_1 = \deg f_2$) looks related to the discrete log problem over $\mathbb{F}_{q^n}$.  The discrete log problem is believed to be hard in general: the fastest algorithms currently known have a subexponential running time, and it is conjectured that there is no polynomial-time algorithm.  In particular, it looks related to the Diffie-Hellman problem, and in most fields the Diffie-Hellman problem is probably as hard as the discrete log problem.  I don't know of a reduction from discrete log or Diffie-Hellman to prove that finding an isomorphism is as hard as those problems, but I suspect there might be some relationship.

I do know that if you can compute the discrete log efficiently in $\mathbb{F}_{q^n}$, then you can exhibit an explicit isomorphism: pick a generator $g$ for the first field, and a generator $h$ for the second field; the isomorphism sends $g \mapsto g'$, and sends $g^k \mapsto h^k$, so given $x$, we compute the discrete log $k$ of $x$ to base $g$, then $x$ maps to $h^k$.

There's lots written about the discrete log problem in such finite fields.  For the case where $q$ is small and $n$ is large, see for example https://crypto.stackexchange.com/q/228/351 and https://crypto.stackexchange.com/q/22332/351.

What about when $f_1,f_2$ are not squarefree?  Then I think the problem is at least as hard.  We can reduce to the case where $f_1 = p_1^e$ and $f_2 = p_2^e$, where $p_1,p_2$ are irreducible and $\deg p_1 = \deg p_2$.  Then I think it might be possible to use Hensel lifting, though I haven't thought through the details.  In particular, here is what happens with the discrete log.  Consider the case where $e=2$.  Let $g=a_1 p_1 + b_1$ be a generator of $\mathbb{F}_q[x]/\langle p_1^2 \rangle$.  Note that

$$g^k = (a_1 p_1 + b_1)^k = k a_1 p_1 + b_1^k.$$

Therefore, to compute the discrete log of $x = a_2 p_1 + b_2$, it suffices to first find $k_0$ such that $b_1^{k_0} = b_2 \pmod{p_1}$ (which is the squarefree case of the discrete log considered above), then find $k$ such that $k \equiv k_0 \pmod{q^n-1}$ and $k \equiv a_2/a_1 \pmod{q^n}$, where $n = \deg p_1$.  Such a $k$ can be found through the Chinese remainder theorem; you end up with $k = k_0 q^n - (a_2/a_1) (q^n-1)$.  This shows how to compute the discrete log in $\mathbb{F}_q[x]/\langle p_1^2 \rangle$ if you know how to compute the discrete log in $\mathbb{F}_q[x]/\langle p_1 \rangle$.
I think the same will apply to any $e&gt;1$, not just $e=2$.