The "shortest possible amount of overhead for describing ciphertexts" is achieved by
FPE ( length(nonce)+length(plaintext) , PRF(key,length(nonce)+length(plaintext)) , nonce || plaintext)
The basic idea is to use independently keyed block ciphers for each possible plaintext length, and include the nonce in what the block ciphers are evaluated on. Since one can't quite independently key the block ciphers, one keys them with the output of a pseudo-random function (such as HMAC) evaluated at their block size. The simple way to include the nonce in what the block ciphers are evaluated on is to concatenate the nonce with the plaintext, so that is done. Finally, to allow the keyholders to extract the plaintext, one puts a prefix-free encoding of the nonce's length at the beginning of the ciphertext.
If you would be using fixed-length nonces, or more generally, if keyholders can efficiently determine length(nonce) from length(nonce)+length(plaintext), then you can skip the prefixfree(length(nonce)) part, since length(nonce)+length(plaintext) would be the length of the ciphertext.
These ciphertexts will always reveal length(plaintext). Unless you skip the first part, these ciphertexts will reveal length(nonce). If a nonce is reused with the same plaintext (and key), then that will be obvious because the ciphertexts will be equal. However, other than the previous two sentences, someone who does not have the key won't know whether or not a nonce was reused.
There another important point. Neither yours nor Stephen's nor my suggestion provide authenticity. (Doing so would require longer ciphertexts.)