Here's my attempt. This gets very messy midway through, so please read it with an eye for catching mistakes (big or little).
Let $\tilde{S}(u,v)=(\tilde{x}(u,v),\tilde{y}(u,v),\tilde{z}(u,v))$ be your original surface with $\tilde{S}(u_0,v_0)=\tilde{s}_0$. The first goal is to translate and rotate so that the surface at $(u_0,v_0)$ has some nicer features.
We'd like to find two nonparallel tangent vectors to $\tilde{S}$ at $\tilde{s}_0$. We could try using $\tilde{S}_u(u_0,v_0)$ and $\tilde{S}_v(u_0,v_0)$, but I'm not sure that these vectors are guaranteed to be nonparallel. Besides, the approach we are about to go with will be useful for the rest of the problem.
Locally around $\tilde{s_0}$, view $\tilde{z}$ as a function of $\tilde{x}$ and $\tilde{y}$. Unless we are very unlucky and the tangent plane to $\tilde{S}$ at $s_0$ is parallel to the $z$-axis, we can do this. Now we compute partial derivatives using the Chain Rule for multivariate functions:
\begin{align*}\frac{\partial\tilde{z}}{\partial\tilde{x}}&=\frac{\partial\tilde{z}}{\partial\tilde{u}}\frac{\partial\tilde{u}}{\partial\tilde{x}}+\frac{\partial\tilde{z}}{\partial\tilde{v}}\frac{\partial\tilde{v}}{\partial\tilde{x}}\\ \Rightarrow\tilde{z}_{\tilde{x}}& =\frac{\tilde{z}_u}{\tilde{x}_u}+\frac{\tilde{z}_v}{\tilde{x}_v}\end{align*}
Similarly, \begin{align*}\tilde{z}_{\tilde{y}}& =\frac{\tilde{z}_u}{\tilde{y}_u}+\frac{\tilde{z}_v}{\tilde{y}_v}\end{align*}
Both of these derivatives can be evaluated at $(u_0,v_0)$ (assuming that we do not have to divide by $0$). This allows us to write down two nonparallel tangent vectors to $\tilde{S}$ at $\tilde{s}_0$:
\begin{align*}\langle 1, 0, {\tilde{z}}_{\tilde{x}}\rangle\end{align*} \begin{align*}\langle 0, 1, {\tilde{z}}_{\tilde{y}}\rangle\end{align*}
These vectors are not orthonormal, but we can use the Gram-Schmidt process to replace them with orthonormal vectors $\vec{p}$ and $\vec{q}$ that span the tangent plane to $\tilde{S}$ at $\tilde{s}_0$. Further, we can find a third orthonormal basis vector for $\mathbb{R}^3$: $\vec{r}=\vec{p}\times\vec{q}$. Using these vectors, we can construct the rotation matrix $M$ that takes the tangent plane to $\tilde{S}$ at $\tilde{s}_0$ to the $xy$-plane. Specifically, $M=\left[\vec{p}\;\vec{q}\;\vec{r}\right]^{-1}$.
Okay, now the whole system can be translated and rotated so that the surface at $(u_0,v_0)$ has tangent plane equal to the $xy$-plane, and so that $\tilde{s_0}$ gets moved to the origin. Let $S(u,v) = M\cdot\left(\tilde{S}(u,v)-\tilde{s}_0\right)$ Note that $S$ is as described.
Similarly, we need to move the original curve. If that was given by $\tilde{C}(t)=(\tilde{i}(t),\tilde{j(t)},\tilde{k}(t))$, let $C(t)=M\cdot\left(\tilde{C}(t)-\tilde{s_0}\right)$
Now comes the hard part. To repeat, we now have a surface $S(u,v)$ with $S(u_0,v_0)$ at the origin and the tangent plane at the origin equal to the $xy$-plane. As a consequence, $c_0$ is somewhere along the $z$-axis. If $S(u,v)=(x(u,v),y(u,v),z(u,v))$ we will again view $z$ as a function of $x$ and $y$. If we can find the three second derivatives of $z$ ($z_{xx}, z_{xy}, z_{yy}$) we can approximate the surface $S$ with the graph of a second degree polynomial.
These second derivatives are not immediately available to us, but they can be found using the Chain Rule for multivariate functions:
\begin{align*}z_{xx} & = \frac{\partial}{\partial x}\left(\frac{\partial z}{\partial x}\right)\\ & = \frac{\partial}{\partial x}\left(\frac{\partial z}{\partial u}\frac{\partial u}{\partial x}+\frac{\partial z}{\partial v}\frac{\partial v}{\partial x}\right)\\ & = \frac{\partial z}{\partial u}\frac{\partial^2 u}{\partial x^2}+\frac{\partial^2 z}{\partial x\partial u}\frac{\partial u}{\partial x}+\frac{\partial z}{\partial v}\frac{\partial^2 v}{\partial x^2}+\frac{\partial^2 z}{\partial x\partial v}\frac{\partial v}{\partial x}\\ & = z_u\frac{\partial}{\partial x}\left(\frac{1}{x_u}\right)+\frac{\partial z_u}{\partial x}\frac{1}{x_u}+z_v\frac{\partial}{\partial x}\left(\frac{1}{x_v}\right)+\frac{\partial z_v}{\partial x}\frac{1}{x_v}\\ & = -\frac{z_u}{x_u^2}\frac{\partial x_u}{\partial x}+\frac{1}{x_u}\frac{\partial z_u}{\partial x}-\frac{z_v}{x_v^2}\frac{\partial x_v}{\partial x}+\frac{1}{x_v}\frac{\partial z_v}{\partial x}\\ & = -\frac{z_u}{x_u^2}\left(x_{uu}u_x+x_{uv}v_x\right)+\frac{1}{x_u}\left(z_{uu}u_x+z_{uv}v_x\right)\\&-\frac{z_v}{x_v^2}\left(x_{uv}u_x+x_{vv}v_x\right)+\frac{1}{x_v}\left(z_{uv}u_x+z_{vv}v_x\right)\\ & = -\frac{z_u}{x_u^2}\left(\frac{x_{uu}}{x_u}+\frac{x_{uv}}{x_v}\right)+\frac{1}{x_u}\left(\frac{z_{uu}}{x_u}+\frac{z_{uv}}{x_v}\right)\\&-\frac{z_v}{x_v^2}\left(\frac{x_{uv}}{x_u}+\frac{x_{vv}}{x_v}\right)+\frac{1}{x_v}\left(\frac{z_{uv}}{x_u}+\frac{z_{vv}}{x_v}\right)\\ \end{align*}
I wouldn't be surprised if this can be reqrouped and simplified. The other two derivatives $z_{yy}$ and $z_{xy}$ can be found similarly. For obvious reasons, I don't want to type them out here.
So...after evaluating at $(u_0,v_0)$, we have the ability to replace $S$ with a second degree approximation $S(x,y)\approx \left\langle x,y,\frac{1}{2}z_{xx}(u_0,v_0)x^2 +z_{xy}(u_0,v_0)xy+\frac{1}{2}z_{yy}(u_0,v_0)y^2\right\rangle$
Lastly, if $C(t)=(i(t),j(t),k(t))$, its projection onto the second degree approximation is $P(t)=\left\langle i(t),j(t),\frac{1}{2}z_{xx}(u_0,v_0)i(t)^2 +z_{xy}(u_0,v_0)i(t)j(t)+\frac{1}{2}z_{yy}(u_0,v_0)j(t)^2\right\rangle$
At this point we have an explicit second degree approximation for the projection of the curve onto the surface in terms of $t$. We can find the curvature for this spacecurve in the standard way.