Daniel Fischer directed me with a few hints to the solution. This happened in comments to the question. I'm posting this to highlight the solution and make it acceptable, so as to get the question off the unanswered.
The first comment said this equality holds for any non-degenerate form, whether it be symmetric, alternating, or neither.
I asked how to prove that, and he answered:
Consider the map $\psi:E\to E^\ast$ given by $\psi(x):(y\mapsto\beta(x,y))$. What does non-degeneracy say about $\psi$? What relation has $\{x:(\forall v\in L)(\beta(x,v)=0)\}$ to $L$ in terms of $\psi$?
The non-degeneracy of $\beta$ implies that if $x\neq0$, $\psi(x)\neq0$, so it is injective, since it is linear, and therefore it is an isomorphism $E\to E^\ast$. As for the set:
$$\{x:v\in L\implies\beta(x,v)=0\}=\{x:v\in L\implies v\in\ker\psi(x)\}=\{x:L\subseteq\ker\psi(x)\}.$$
But that got me stuck again. And Daniel commented:
Do you remember what an annihilator is?
Sort of. I remembered the name, but from another setting. I never used annihilators in linear algebra, only those of rings in abstract algebra. Anyway that set is:
$$\{x:\psi(x)\in L^0\},$$
$L^0$ denoting the annihilator of $L$. Wikipedia came in here with:
If $W$ is a subspace of $V$ then the quotient space $V/W$ is a vector space in its own right, and so has a dual. By the first isomorphism theorem, a functional $f : V \to F$ factors through $V/W$ if and only if $W$ is in the kernel of $f$. There is thus an isomorphism
$$(V/W)^\ast \cong W^0.$$
As a particular consequence, if $V$ is a direct sum of two subspaces $A$ and $B$, then $V^\ast$ is a direct sum of $A^0$ and $B^0$.
Assuming the isomorphism exists, we obtain that $\dim(V/L)^\ast=\dim L^0$, but $V/L$ is canonically isomorphic to its dual as any finite-dimensional vector space, and so:
$$\dim L^0=\dim(V/L)^\ast=\dim V/L=\dim V-\dim L,$$
which is precisely the desired equality.
We are left with the isomorphism to prove. Suppose $f\in L^0$. Since $L\subseteq\ker f$, the map $\phi(f)\in(V/L)^\ast$ defined by $\phi(f)(v+L)=f(v)$ is well-defined and linear, so $\phi:L^0\to(V/L)^\ast$. Linearity is straightforward from the definition, so if $\ker\phi=\{0\}$ and the dimensions are equal (or $\phi$ is surjective) we are done. That the kernel is trivial is easy. Suppose $\phi(f)(v+L)=0$ for all $v+L$. This means $f(v)=0$ for all $v$, so $f=0$. Thus, the kernel is trivial. We can construct the inverse of $\phi$ explicitly. Let $\chi$ be the map that, given $f\in(V/L)^\ast$, maps it to $\chi(f)$ defined by $\chi(f)(v)=f(v+L)$. This new map is well-defined, and linear, so $\chi:(V/L)^\ast\to L^0$. Indeed, because by definition the maps produced by $\chi$ map all $L$ into zero, since $\chi(f)(v)=f(v+L)$, and if $v\in L$, $v+L=0+L$. This is clearly the inverse of $\phi$, as can be checked by trivial computations. So $\phi$ is indeed an isomorphism, and our proof is over.
Note: If you read the comments, you will see I forgot the surjectiveness, or rather implicitly assumed it. It was forgetfulness, and the surjectiveness needed consideration.