What do we know about the growth rate of $C(n)$?
We know the exact value of $C(n)$ if, in its definition,
we restrict to the class of distributive lattices.
Otherwise we only have partial results. Let me say a few words.
Claim.
If $L$ is a finite distributive that has a maximal chain
$\ell_1<\ell_2<\cdots < \ell_n$, then
- $L$ is representable as the
congruence lattice of an algebra of size $n$, and
- $L$ is not representable as the congruence
lattice of any algebra of size $< n$.
Reasons:
For for the first item, observe that
if $L$ is a finite distributive lattice
with a specified maximal chain
$\gamma: \ell_1<\ell_2<\cdots < \ell_n$,
then it has a $0,1$-embedding into a Boolean lattice $B$
in such a way that the chain $\gamma$ remains a maximal chain.
Next, any Boolean lattice $B$ with an $n$-element
maximal chain is isomorphic to a power-set
lattice $\mathscr{P}(S)$ where
$S=\{s_1,\ldots,s_{n-1}\}$ is a set of size $n-1$.
Assume that $0\notin S$.
Next,
$\mathscr{P}(S)$ can be embedded into the lattice
$\Pi(\{0\}\cup S)$ of partitions of $\{0\}\cup S$
by mapping $U\subseteq S$ to the partition where $\{0\}\cup U$
is one cell and the other cells are singletons.
This is a $0,1$-embedding.
Altogether we have $0,1$-embeddings
$L\leq B\cong \mathscr{P}(S)\leq \Pi(\{0\}\cup S)$,
which compose to a $0,1$-embedding of
$L$ into a partition lattice
on a set of size $|\{0\}\cup S|=n$.
From here we cite
Quackenbush, R.; Wolk, B.
Strong representation of congruence lattices.
Algebra Universalis 1 (1971/72), 165-166.
which shows that any $0,1$-distributive sublattice $L$
of the lattice of the lattice of equivalence relations
on an $n$-element set is a representation of $L$
as a congruence lattice.
For the second item of the claim, it is impossible
to represent any lattice $L$ with a maximal chain
of $n$-elements as a congruence lattice
on a set of size $k<n$, since the full
lattice of partitions on a $k$-element set
does not have a chain of $n$ elements.
In particular, if we relativize the definition
of $C(n)$ to the class of distributive
lattices, we get the following.
Let $C_{\textrm{Dist}}(n)$ be
the least $k$ such that every bounded distributive
lattice with cardinality $\leq n$ which is isomorphic
to the congruence lattice of some finite algebra,
is isomorphic to the congruence lattice of some
algebra with cardinality $k$.
With this definition and the preceding remarks,
we get $C_{\textrm{Dist}}(n)=n$. (If you look
at all bounded distributive
lattices with cardinality $\leq n$,
they are all representable, and the hardest
to represent is the $n$-element chain.
This can be represented as the congruence lattice
of an $n$-element algebra, but of no smaller algebra.)
What I said above about distributive lattices
can be extended a little bit.
A finite distributive lattice is a sublattice
of a power of the $2$-element lattice, $\mathbf{2}$.
The same kinds of results mentioned above can be proved for
the smallest nondistributive lattices
$M_3$ and $N_5$. Namely, $M_3$ can be represented as a congruence
lattice on a $3$-element set, $N_5$ can be represented
as a congruence lattice on a $4$-element set, and any sublattice
of a power of either representation is a congruence representation.
For this see
Snow, John W.
Every finite lattice in $\mathscr{V}(M_3)$
is representable.
Algebra Universalis 50 (2003), no. 1, 75-81.
and
Snow, John W.
Subdirect products of hereditary congruence lattices.
Algebra Universalis 54 (2005), no. 1, 65-71.
When you move to $M_4$, it starts to get complicated, as is
explained in an answer to an earlier question.
In fact, it is not hard to produce a $0,1$-embedding of
$M_q$ into the lattice of partitions of a $q$-element
set whenever $q$ is an odd prime, but the least size
congruence representation of $M_{p+1}$ has
size $2p$ when $p$ is an odd prime. Thus, if $p$ and $q$
are odd primes satisfying $p<q<2p$, then there
is a $0,1$-embedding of $M_{p+1}$ into $M_q$
and then into the lattice
of partitions of a $q$-element set, but there is
no congruence representation of $M_{p+1}$ on a $q$-element set.
Let me jump ahead to identify what seems to be the hardest
part of this problem. In
Pálfy, Péter Pál; Pudlák, Pavel
Congruence lattices of finite algebras and
intervals in subgroup lattices of finite groups.
Algebra Universalis 11 (1980), no. 1, 22-27.
Palfy and Pudlak isolate three properties of a
finite bounded lattice $L$ of size strictly
greater than $2$:
(A) $L$ is simple.
(B) For any nonzero $x\in L$ there exist
$y_1, y_2\in L$ such that $x\vee y_1=x\vee y_2=1$
and $y_1\wedge y_2=0$.
(C) Any $x\in L$ that is not zero and not an atom
dominates at least $4$ atoms.
Palfy and Pudlak show two things about these properties.
They show that if $L$ is any finite lattice,
then it can embedded as an upper
interval $[u,1]$ in a lattice $L'$ which satisfies
(A), (B), and (C) and has size $|L'|=5|L|+1$.
If one can represent $L'$ as a congruence
lattice of a finite algebra $\mathbf{A}$, then one
can represent $L$ as the congruence lattice
of $\mathbf{A}/u$. Thus, $L'$
(satisfying (A), (B), (C)) is only slightly larger
than $L$ (not necessarily satisfying (A), (B), (C)),
yet any upper bound on the size
of a minimal congruence lattice representation for $L'$
is also an upper bound on the size
of a minimal congruence lattice representation for $L$.
Second, they show that if $L$
satisfies (A), (B), and (C)
and $L$ is representable as the congruence
lattice of a finite algebra $\mathbf{A}$, then there
is representation of $L$ as the congruence lattice
of a transitive $G$-set $\mathbf{B}$ satisfying $|B|\leq |A|$.
This says that, if $L$ is sufficiently complicated
and representable as a congruence lattice, then it
is representable as the congruence lattice of
a transitive $G$-set for some finite group $G$.
Such $G$-sets are isomorphic to $G/H$
under the action of left multiplication by elements of $G$
for some subgroup $H\leq G$.
Hence, if $L$ satisfies the conditions (A), (B), and (C),
and $L$ is representable as the congruence
lattice of a finite algebra, then a minimal
congruence representation may be assumed
to be of the form of a transitive $G$-set $G/H$
of size $|B|=[G:H]$, and the lattice $L$
will be isomorphic to interval in $\textrm{Sub}(G)$
of subgroups containing $H$.
If we try to estimate $C(n)$
for some $n$ equal to the size of some
Palfy-Pudlack lattice (defined as satisfying
their conditions (A), (B), (C)), we
find that we are asking for the least
index $[G:H]$ in a finite group
if the interval in $\textrm{Sub}(G)$
of subgroups containing $H$ has size $n$.
The work of Palfy and Pudlak suggests that the hard
lattices to represent are those satisfying (A), (B), and (C).
If $L$ is such a lattice, which is representable
as a congruence lattice and it has size $n$,
then to compute $C(n)$ we must be able to
determine $[G:H]$ where $G/H$
is the smallest algebra affording a congruence
representation of $L$.
This has been attempted for the sequence
of lattices $L=M_n$, for which see
Baddeley, Robert; Lucchini, Andrea
On representing finite lattices as intervals
in subgroup lattices of finite groups.
J. Algebra 196 (1997), no. 1, 1-100.
They give $G$-set congruence
lattice representations for $M_n$ for
$n$ of the form
$1, 2, q+1, q+2, ((q^t+1)/(q+1))+1$,
$q$ a prime power. I believe that it is still
unknown whether $M_n$ is representable for other
values of $n$.
