Message-Recovery variant of Ed25519 signature?
Fix finite fields $k$ and $k'$, say $k = \mathbb F_p$ and $k' = \mathbb F_{p^2}$ represented by $\mathbb F_p[i]/(i^2 + 1)$ where $$p = 36 u^4 + 36 u^3 + 24 u^2 + 6 u + 1$$ for $u = -2^{62} - 2^{55} - 1$.  Fix a group $G$ written multiplicatively, say $(\mathbb F_{p^{12}})^\times$.  Fix elliptic curves $E/k$ and $E'/k'$, say $E/k : y^2 = x^3 + 2$ and $E'/k' : y^2 = x^3 + 2/(1 + i)$, with a bilinear map $e\colon E(k) \times E'(k') \to G$, say the Tate pairing.  Fix a random function $H\colon \{0,1\}^* \to E(k)$, say $m \mapsto {+}x^{-1}(\operatorname{SHA256}(m))$, where ${+}x^{-1}(x_0)$ is the point on $E(k)$ with $x$ coordinate $x_0$ and the lexicographically smallest $y$ coordinate.  Fix a point $G \in E'(k')$ of large prime order.  (This choice of curve $E/k$ and its twist $E'(k')$ is more popularly known as BN(2, 254).)

A public key is the byte encoding $\underline A$ of a point $A$ on $E'(k')$.  A signature of a message $m$ under $\underline A$ is the byte encoding $\underline\sigma$ of an element $\sigma \in E(k)$ satisfying $$e(\sigma, G) = e(H(\underline A \mathbin\Vert m), A).$$

A private key is the byte encoding $\underline a$ of a secret scalar $a$; the corresponding public key is $\underline A = \underline{[a]G}$.  To sign a message $m$ with private key $\underline a$, the signer computes $\sigma = [a]H(A \mathbin\Vert m)$.  This yields a signature because
\begin{align*}
  e(\sigma, G)
    &amp;= e([a]H(\underline A \mathbin\Vert m), G) \\
    &amp;= e(H(\underline A \mathbin\Vert m), G)^a \\
    &amp;= e(H(\underline A \mathbin\Vert m), [a]G) \\
    &amp;= e(H(\underline A \mathbin\Vert m), A)
\end{align*}
by the bilinearity of $e$.

Note that in the choice of parameters above, a signature can be encoded in 32 bytes, or even a mere 255 bits, by combining a 254-bit encoding of an $x$ coordinate with a single bit to discriminate between the two possible $y$ coordinates.  (Further compression of the curve points may be possible with techniques like Decaf, left as an exercise for the reader.)

Thus, you have 32 bytes and 1 bit left in your budget for a 64-byte Ed25519 signature to encode a part of the message, thereby enabling message recovery of 32 bytes (plus 1 bit) in 64-byte signatures!

Let us then define a Mr. Signature as a 64-byte string $\underline \sigma \mathbin\Vert m$ satisfying $$e(\sigma, G) = e(H(\underline A \mathbin\Vert m), A),$$ which admits message recovery by $\underline \sigma \mathbin\Vert m \mapsto m$.

(Am I joking?  Maybe!)