Post-quantum alternative to ElGamal? (public key verifiability)
There is nothing quite meeting your requirements, especially if you require the ability to generate random valid public keys without knowing the corresponding private key. CSIDH (not a NIST candidate) comes closest, in that you can at least generate random private keys and easily publish the corresponding public keys verifiably.