Here are two alternatives to ECDSA which was already mentioned:
RSA-PSS with message recovery -- RSA signatures are at least as long as the modulus. But RSA-PSS with message recovery allows to pack part (or all) of the data you want to sign into the signature itself. Verification of RSA signatures is also pretty fast. If the message you want to sign is not much shorter than the RSA modulus the size overhead will be very small. (See example below)
EdDSA -- also a method based on an elliptic curve, but supposedly faster and easier to implement in a safe way than ECDSA. These kinds of signatures take up 4s bits for a security of s bits.
Example for RSA-PSS with message recovery:
- RSA modulus: 3072 bits
- hash: SHA-256
- salt: 64 random bits
Then, the signature of 3072 bits (384 bytes) stores a 256 bit hash (32 bytes), a 64 bit salt (8 bytes), and two fixed bytes (I think). That leaves room for up to 342 message bytes. So, for a message of at least 342 bytes you'll have an overhead of only 42 bytes (336 bits) at a security level of "128" (not "80").