Because it's too long for a comment I'll post this as an answer: I just want to provide Omar Antolín's nice proofs of the following facts. These facts probably go back to this paper:
but Lovász did not phrase them using category theory.
Theorem 1. Suppose $T$ is a Lawvere theory having finitely many isomorphism classes of algebras of cardinality $n$ for each $n \in \mathbb{N}$. If $(a_n)_{n \ge 0}$ is the number of isomorphism classes of algebras of cardinality $n$, then
$$ a_{n^k} \ge a_n $$
for each $n, k \in \mathbb{N}$.
This follows easily from
Theorem 2. Let $A, B$ be two algebras of a Lawvere theory whose underlying sets are finite. If $A^k \cong B^k$ for some natural number $k$ then $A \cong B$.
Theorem 2 in turn follows from this lemma:
Super-Yoneda Lemma. Let $\mathsf{C}$ be the category of algebras of some Lawvere theory, and let $A, B \in \mathsf{C}$ be two algebras whose underlying sets are finite. If the functors $\mathrm{hom}(-,A)$ and $\mathrm{hom}(-,A)$ are unnaturally isomorphic, then $A \cong B$.
Here we say the functors $\mathrm{hom}(-,A)$ and $\mathrm{hom}(-,B)$ are unnaturally isomorphic if
$$ \mathrm{hom}(X,A) \cong \mathrm{hom}(X,B) $$
for all $X \in \mathsf{C}$. We're not imposing the usual naturality condition involving a commuting square — indeed we can't, since we're not even giving any specific choice of isomorphism!
If $A$ and $B$ are objects in any category and $\mathrm{hom}(-,A)$ and $\mathrm{hom}(-,B)$ naturally isomorphic, we can show $A \cong B$ using the Yoneda Lemma. But when they're unnaturally isomorphic, we need to use the Super-Yoneda Lemma, which has more restrictive hypotheses.
Here's how the Super-Yoneda Lemma implies Theorem 2.. Since $A^k \cong B^k$, we have natural isomorphisms
$$ \mathrm{hom}(-,A)^k \cong \mathrm{hom}(-, A^k) \cong \mathrm{hom}(-, B^k) \cong \mathrm{hom}(-,B)^k $$
so for any $X \in \mathsf{C}$ the sets $\mathrm{hom}(X,A)^k$ and $\mathrm{hom}(X,B)^k$ have the same cardinality. This means we have an unnatural isomorphism
$$ \mathrm{hom}(-,A) \cong \mathrm{hom}(-,B) $$
The lemma then lets us conclude that
$$ A \cong B $$
Next let's turn to the lemma. I'll just quote Omar Antolín's proof, since I can't improve on it. Remember, $A$ and $B$ are algebras of some Lawvere theory whose underlying sets are finite:
Let $\mathrm{mon}(X, A)$ be the set of monomorphisms, which here are just homomorphisms that are injective functions. I claim you can compute the cardinality of $\mathrm{mon}(X, A)$ using the inclusion-exclusion principle in terms of the cardinalities of $\mathrm{hom}(Q, A)$ for various quotients of $X$.
Indeed, for any pair of elements $x, y \in X$, let $S(x, y)$ be the set for homomorphisms $f \colon X \to A$ such that $f(x) = f(y)$. The monomorphisms are just the homomorphisms that belong to none of the sets $S(x, y)$, so you can compute how many there are via the inclusion-exclusion formula: you'll just need the cardinality of intersections of several $S(x_i, y_i)$.
Now, the intersection of some $S(x_i, y_i)$ is the set of homorphisms $f$ such that for all $i$, $f(x_i) = f(y_i)$. Those are in bijection with the homorphisms $Q \to A$ where $Q$ is the quotient of $X$ obtained by adding the relations $x_i=y_i$ for each $i$.
So far I hope I've convinced you that if $\mathrm{hom}(-, A)$ and $\mathrm{hom}(-, B)$ are unnaturally isomorphic, so are $\mathrm{mon}(-, A)$ and $\mathrm{mon}(-, B)$. Now it's easy to finish: since $\mathrm{mon}(A, A)$ is non-empty, so is $\mathrm{mon}(A, B)$, so $A$ is isomorphic to a subobject of $B$. Similarly $B$ is isomorphic to a subobject of $A$, and since they are finite, they must be isomorphic.
If you examine this argument you'll see we didn't use the full force of the assumptions. We didn't need $A$ and $B$ to be algebras of a Lawvere theory. They could have been topological spaces, or posets, or simple graphs, or various other things. It seems all we really need is a category $\mathsf{C}$ of gadgets with a forgetful functor
$$ U \colon \mathsf{C} \to \mathsf{FinSet} $$
that is faithful and has some extra property... roughly, that we can take an object in $\mathsf{C}$ and take a quotient of it where we impose a bunch of extra relations $x_i = y_i$, and maps out of this quotient will behave as you'd expect. More precisely, I think the extra property is this:
Given any $X \in \mathsf{C}$ and any surjection $p \colon U(X) \to S$, there is a morphism $j \colon X \to Q$ such that the morphisms $f \colon X \to A$ that factor through $j$ are precisely those for which $U(f)$ factors through $p$.
I would like to understand this better. This paper should help:
but I haven't had time to absorb it yet. Here's the abstract:
A classical result due to Lovasz (1967) shows that the isomorphism type of a graph is determined by homomorphism counts. That is, graphs $G$ and $H$ are isomorphic whenever the number of homomorphisms from $K$ to $G$ is the same as the number of homomorphisms from $K$ to $H$ for all graphs $K$. Variants of this result, for various classes of finite structures, have been exploited in a wide range of research fields, including graph theory and finite model theory.
We provide a categorical approach to homomorphism counting based on the concept of polyadic (finite) set. The latter is a special case of the notion of polyadic space introduced by Joyal (1971) and related, via duality, to Boolean hyperdoctrines in categorical logic. We also obtain new homomorphism counting results applicable to a number of infinite structures, such as finitely branching trees and profinite algebras.
