I think Graham's answer already gave most of what you need to prove that $4$ is  the smallest possible. Let $V$ be the integral closure of $R$, $n$ be the embedding dimension of $R$, and $e=e(R)$ be the multiplicity. 

Claim: If $R=k[[x_1,\cdots,x_n]]/I$ is Gorenstein and $n$ is  at least $3$, then $\dim_k(V/R)\geq e$. 

Proof: Let $m$ be the maximal ideal of $R$. As Graham pointed out, we have $e = \dim_k(V/mV)$. So:

$$\dim_k(V/R) =\dim_k(V/mR)-\dim_k(R/mR) \geq \dim_k(V/mV)-1=e-1$$ 

We need to rule out the equality. If equality happens, then one must have $mV=mR$. This shows that $m$ is the conductor of $R$. As you already knew, since $R$ is Gorenstein, one must then have $\dim_k(V/R)=\dim_k(R/m)=1$. The inequality now gives $e\leq 2$. Abhyankar's inequality (part 2 of Graham's answer) gives $n\leq 2$, so $R$ is planar, contradiction. 

Now, one needs to show that for $R$ non-planar, $e\geq 4$. You could use part $3$ of Graham's answer, or arguing as follows: if $n\geq 4$ we are done by Abhyankar inequality. If $n=3$, a Gorenstein quotient of $k[[x,y,z]]$ must be a complete intersetion, and so $I=(f,g)$, each of minimal degree at least $2$ since $R$ is not planar, thus $e$ must be at least $4$. 

By the way, one could construct a *domain* $R$ such that $\dim_k(V/R)=4$ as follows: 
Take $R=k[[t^4,t^5,t^6]]$. The semigroup generated by $(4,5,6)$ is symmetric, so $R$ is Gorenstein. The Frobenius number is $7$, and $V/R$ is generated by $t,t^2,t^3,t^7$.