Here is a construction of a "universally-embedding locally small category", assuming we are in a context (such as NBG) with the axiom of choice and where all proper classes have the same size (hence can be well-ordered with order-type $\mathrm{Ord}$, the proper class of (small) ordinals). In a universe-based approach to size, R. Street has used the term "moderate" for a category whose size is no larger than that of the universe; thus this can be interpreted in such a context as a universally-embedding locally small *moderate* category.

Define a transfinite sequence of *small* categories $W : \mathrm{Ord} \to \mathrm{Cat}$ by transfinite induction as follows. At limit steps, take colimits (including $W_0 = \emptyset$). At a successor step, suppose $n$ is an ordinal and $W_n$ is defined, and let $S_n$ be a set of representatives of isomorphism classes of spans $B \leftarrow A \to W_n$, where $A\to W_n$ is a full subcategory inclusion, $A\to B$ is a fully faithful inclusion that misses exactly one object, and the objects and arrows of $B$ have cardinality $<\aleph_n$. The cardinality restriction ensures that $S_n$ is indeed a set rather than a proper class. Now let $W_{n+1}$ be the pushout in $\mathrm{Cat}$:

$$ \begin{array}{ccc} \coprod_{s\in S_n} A_s & \to & \coprod_{s\in S_n } B_s \\ \downarrow && \downarrow \\ W_n & \to & W_{n+1} \end{array} $$

I claim that $W_n \to W_{n+1}$ is fully faithful, as are each of the functors $B_s \to W_{n+1}$. This follows by observing that $W_{n+1}$ can equivalently be constructed as a *small* transfinite composite of pushouts, if we well-order $S_n$:

$$\begin{array}{ccccccccccccccc}
& & A_{s_0} & \to & B_{s_0} &&&& A_{s_1} & \to & B_{s_1} \\
& \swarrow &&&& \searrow && \swarrow &&&& \searrow\\
W_n &&& \longrightarrow &&& W_{n,1} &&& \longrightarrow &&& W_{n,2} &\to & \dots
\end{array}$$

and the fact that fully faithful inclusions are closed under pushouts and transfinite composites.

Now let $W_\infty$ be the transfinite composite of the sequence $W : \mathrm{Ord} \to \mathrm{Cat}$. Since this is a large colimit, $W_\infty$ is a large category. But since it is a transfinite composite of fully faithful inclusions of small categories, $W_\infty$ is locally small, and moreover each inclusion $W_n \to W_\infty$ is fully faithful.

I claim that $W_\infty$ is a universally-embedding locally small category. Suppose $C$ is a locally small category. Well-order its objects as $\{c_n\}_{n\in \mathrm{Ord}}$ (here is where we use the fact that all proper classes have the same size), and let $C_n$ be the (small!) full subcategory of $C$ on the objects $\{c_k\}_{k<n}$. Then $C$ is the transfinite composite of the $C_n$'s, so by transfinite induction it suffices to show that any full embedding of $C_n$ into $W_\infty$ can be extended to $C_{n+1}$.

Since $C_n$ is small, there exists an ordinal $m$ such that the embedding $C_n \to W_\infty$ factors through $W_m$. Moreover, by enlarging $m$ if necessary we may assume that $C_{n+1}$ has cardinality $<\aleph_m$. Therefore, the span $C_{n+1}\leftarrow C_n \to W_m$ is isomorphic to some span $B \leftarrow A \to W_m$ in $S_m$, and therefore the composite $C_n \to W_{m} \to W_{m+1}$ extends to a full embedding of $C_{n+1}$ (the embedding $B\to W_{n+1}$ arising from the definition of the latter as a pushout). This completes the proof.

Of course, this construction is rather tautological and not very interesting, at least not compared to the more contentful embedding theorems about algebraic categories mentioned in the question. However, it does show that such a category exists.