Signing many small messages with minimal overhead
Then, in the next message, include that random value and a new hash of another random value.


What would prevent someone from taken that valid 'next message', replacing the contents with their own message, and keeping the random value in place?

You could define a hash chain by hashing the entire message to come up with the previous value, but this would imply that when you sent the initial message, you already knew all the other messages at that time; that's unlikely to be a workable assumption.

Alternatives that immediately come to mind:


Use ECDSA (or EdDSA) signatures; those are only 64 bytes (for 128 bit security)
Consider using the Tesla protocol to do the authentication; it works similar to yours, except the actual signature comes at the end, not the beginning (and the receiver isn't sure that the messages are authentic until it receives that final message).