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$. 
  
EDIT (references, per OP's request): Abhyankar inequality is standard, for example see Exercise 4.6.14 of Bruns-Herzog "Cohen-Macaulay rings", second edition ([Link to the exact page](http://books.google.com/books?id=ouCysVw20GAC&lpg=PP1&dq=cohen%20macaulay%20rings&pg=PA192#v=onepage&q&f=false)). Or see exercise 11.10 of [Huneke-Swanson book](http://books.google.com/books?id=APPtnn84FMIC&lpg=PP1&ots=2LcMcV9DU0&dq=Huneke%20Swanson%20book&pg=PA233#v=onepage&q&f=false), also available for free [here](http://people.reed.edu/~iswanson/book/index.html). Or Google "rings with minimal multiplicity".

As for $e=\dim_k(V/mV)$, I could not find a convenient reference, but here is a sketch of proof using the above reference: First, using the additivity and reduction formula (Theorem 11.2.4 of Huneke-Swanson) to reduce to the domain case. Assume that $R$ is now a complete domain, then $V=k[[t]]$, and $R$ is a subring of $V$. Let $x\in m$ be an element with smallest minimal degree. Then $mV=xV$ ($V$ is a DVR), and it is not hard to see that $e=$ the minimal degree of $x$ $=\lambda(V/xV)$ (see Exercise 4.6.18 of Bruns-Herzog, same page  as the link above).