This is not really an answer, but it's too long for a comment: since Alex was asking for bound in terms of numerical invariants, I'll try to give another point of view (which will be certainly less precise of Harris' result explained by jvp) which could perhaps be of some interest.

Let $S$ be a smooth surface and suppose $A\to X$ is an ample line bundle. Then some multiple $m_0 A$ of $A$ will give an embedding of $S$ in some projective space $\mathbb P^N$. After the embedding, the very ample line bundle $m_0 A$ "becomes" isomorphic tautologically to the restriction $\mathcal O_X(1)$ of $\mathcal O(1)$ to $X$, and the degree of $S$ relative to this embedding is just $\mathcal O_X(1)^2=m_0^2 A^2$.

Now, given an ample line bundle $A$ on a $n$-dimensional smooth projective manifold, an important problem of algebraic geometry is to find effective bounds $m_0$ such that multiples $mA$ of $A$ become very ample for $m \ge m_0$ . From a theoretical point of view, this problem has been solved by Matsusaka and Kollár-Matsusaka. Their result is that there is a bound $m_0 = m_0 (n, A^n, A^{n−1}\cdot K_X )$ depending only on the dimension and on the first two coefficients $A^n$ and $L^{n−1}\cdot K_X$ in the Hilbert polynomial of $A$.

Later on, Siu gave an effective version of the Big Mastusaka theorem, which reads as follow:

**Theorem. (Siu '93).** Let $A$ be an ample holomorphic line bundle over a compact complex manifold $X$ of complex dimension $n$ with canonical line bundle $K_X$. Then $mA$ is very ample for 
$$
m\ge m_0:=\frac{(2^{3^{n-1}}5n)^{4^{n-1}}(3(3n-2)^nA^n+K_X\cdot L^{n-1})^{4^{n-1}3n}}{(6(3n-2)^n-2n-2)^{4^{n-1}n-\frac 23}(A^n)^{4^{n-1}3(n-1)}}.
$$

Thus, if you fix any polarization on your (abstract) manifold, then you get a lower bound on the degree of the embedding with respect to this polarization only in numerical terms.