<a href="http://en.wikipedia.org/wiki/Sard's_theorem">Sard's Theorem</a>, which is foundational, may be an example of a theorem of the sort you are looking for when the differentiability class of the function is low. Let's recall its classical statement:

<blockquote>
<b>Sard's Theorem</a>: Let $f\colon\, \mathbb{R}^n\to\mathbb{R}^m$ be a $k$ times continuously differentiable function, where $k\geq \text{max}(n-m+1,1)$. Let $X$ be the critical set of $f$. Then $f(X)$ has Lebesgue measure $0$ in $\mathbb{R}^m$.
</blockquote>

A constructivist version was proven by Yuen-Kwok Chan in 1971:

<blockquote>
Chan, Yuen-kwok, <i>A constructive proof of Sard's theorem.</i> Pacific J. Math. <b>36</b>, 291–301 (1971; MR0276988).
</blockquote>

The constructivist version relaxes the statement of Sard's theorem in a benign way ("critical points" are replaced by "almost critical points") and in at least one less benign way:
<blockquote> 
The function $f$ is taken to be a $k$ times continuously differentiable function, where $k\geq 2+\frac{1}{2}(n-m)(n-m+1)$.
</blockquote>
I can imagine this being a real issue, because the function actually given to you might be $C^k$ for
$\text{max}(n-m+1,1)\leq k< 2+\frac{1}{2}(n-m)(n-m+1)$. John Milnor on <a href="http://www.ams.org.ezlibproxy1.ntu.edu.sg/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=TI&pg6=PC&pg7=ALLF&pg8=ET&r=1&review_format=html&s4=Chan&s5=sard%27s&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq">Mathematical Reviews</a> asks whether the bound on $k$ can be tightened, and so does the author at the end of the paper. If not, then Sard's Theorem for small $k$ seems to me to be a genuinely important result which can be proved classically, but not constructively.