Assuming your protocol is stateful (i.e. you only need to send the parameters - such as the nonce/IV - once), then the overhead of using an AE mode should be very small. CCM for instance has a fixed overhead of as little as
4 bytes (depends on the desired MAC size). Since the minimum size of a TCP/IP packet is
40 bytes, that's a maximum
10% increase in size (for the empty message). By contrast, the SHA256 HMAC alone needs
32 extra bytes.
Disclaimer: I'm not really experienced enough to say if this is enough to achieve the security properties you need. In an answer to one of my earliest (and stupidest) questions, Tom Leek said:
An open SSL connection implies a very slight overhead compared with raw unprotected data: in practice, about 30 extra bytes per record (it depends on the cipher suite), each record able to hold up to 16384 bytes of data, so we are talking about less than 0.2% of size increase, and you would get that with any other protocol which ensures confidentiality and integrity anyway.
Since an AE mode should provide "confidentiality, integrity and authenticity", then something must be wrong here (did I forget something that must be sent besides the ciphertext on each message? or is it because of the "stateful" requirement?)