Minimizing residual finite state automata
Let the "DFA $\to$ NFA" problem denote the following: Given a DFA $A$ and an integer $k$, is there an NFA with at most $k$ states equivalent to $A$? Similarly, let "DFA $\to$ RFSA" denote the problem obtained from the above if we replace "NFA" with "residual finite state automaton".

Jiang and Ravikumar showed that the "DFA $\to$ NFA" problem is PSPACE-complete by a reduction from the "DFA union universality" problem. The latter problem has given a list of DFAs $A_1,A_2,\ldots,A_n$, and asks if $\bigcup_{i=1}^nL(A_i) = \Sigma^*$. 

Their reduction goes by defining a language $L$ from these DFAs and a suitable integer $k$, such that a DFA accepting $L$ can be constructed in time polynomial in the size of the DFAs $A_i$. Then they show that every NFA (thus a fortiori every RFSA) accepting $L$ needs at least $k$ states in case $\bigcup_{i=1}^nL(A_i)$ is universal and at least $k+1$ states otherwise. Then they construct a $k$-state NFA $N$, which accepts $L$ iff $\bigcup_{i=1}^nL(A_i) = \Sigma^*$. 

This proof was reconsidered later by Gruber and Holzer (Developments in Language Theory '06). They use the same reduction to show a slightly different result, which concerns the computational complexity of lower bound techniques for NFAs: An (extended) fooling set for a regular language $R$ is a set $S$ of word pairs $(x_i,y_i)$, such that for each $i$ holds $x_iy_i\in L$ but for all $i\neq j$ holds: $x_iy_j \notin R$ or $x_jy_i\notin R$.

For the above reduction, they show that there is an extended fooling set $S$ of size $k$ in case $\bigcup_{i=1}^nL(A_i)$ is universal. By inspecting the proof by Gruber and Holzer, one readily notes that each "left word" $x_i$ in the set $S$ is such that the NFA $N$ mentioned above can go from the initial state to only a single state $q_i$ on reading $x_i$. That is, the language accepted from state $q$ equals $x_i^{-1}L$, and thus $N$ is a residual finite state automaton.

If the above reasoning contains no mistakes, this yields a reduction from the DFA union universality problem to the "DFA $\to$ RFSA" problem, and thus it is PSPACE-hard. Membership in PSPACE follows along the same lines as for the DFA $\to$ NFA problem, so the "DFA $\to$ RFSA" problem is PSPACE-complete. Being more general but still in PSPACE, the "NFA $\to$ RFSA" problem is PSPACE-complete as well. 

For those who want to reconstruct the above argument (please don't take it for granted, my writeup was a bit hasty), I recommend reading the proof of Theorem 15 in the ECCC report cited below. Especially, Figure 5 on page 18 depicts the automaton $N$ which I claim to be a RFSA. 

T. Jiang and B. Ravikumar. Minimal NFA problems are hard. SIAM Journal on
Computing, 22(6):1117–1141, December 1993.

Hermann Gruber and Markus Holzer. Finding Lower Bounds for Nondeterministic State Complexity Is Hard. In Oscar H. Ibarra and Zhe Dang, editors, 10th International Conference on Developments in Language Theory (DLT 2006), Santa Barbara (CA), USA, volume 4036 of Lecture Notes in Computer Science, pages 363--374. Springer, June 2006. 

Hermann Gruber and Markus Holzer. Finding Lower Bounds for Nondeterministic State Complexity is Hard. Technical Report ECCC TR06-027, Electronic Colloquium on Computational Complexity, 2006.