If you "decrypt with a public key" then it is not "encrypted" in the usual sense, since the public key is public: anybody can use the public key, and, therefore, the message cannot be considered confidential in any way.
For the message confidentiality to be preserved, the decryption operation must be available only to the receiver, and, as such, MUST use some value that only the receiver knows -- as it were, a private key (or, at least, a secret shared between sender and receiver). Similarly, for the message integrity to be verifiable, power of sending a message which can be validated MUST be limited to the sender. There again, a secret value must exist, but on the sender side this time (or, again, as a secret shared between sender and receiver).
Shared secrets are expensive to distribute. Asymmetric cryptography is about solving that. The classical solution is to use an asymmetric key exchange (with the receiver's public key) and to add a signature (with the sender's private key). The key produced by the key exchange algorithm is then a shared secret sufficient to do symmetric encryption. Deployed, well-vetted algorithms would be:
for a total size overhead of 96 bytes. I am using the usual "128-bit" security level which is safe against tomorrow's three-letter agencies; that's then 256 bits for the ECDH, 512 bits for ECDSA. AES-CTR will induce no extra overhead, assuming that each message has its own ECDH key exchange: this allows us to use a fixed, constant IV, and the ECDSA signature nullifies the need for a MAC.
Important warning: it is not totally obvious to slap all these algorithms together, depending on the security properties to be achieved. If you need the signature to be a proof verifiable by a third party, e.g. a judge, then the signature will need to be computed over the cleartext data, but this may leak information on that data. Also, to avoid replay attacks, you might want to include a sequence number in the signature computation. Please exercise caution; I am here describing possibilities, but specification would need more thinking.
Can we do better ? Yes we can; there are several ways. The generic problem of efficiently combining public-key encryption (or key exchange) with a signature is called signcryption. This is still rather new, so no standard way has emerged yet.
In practice, you can reduce the signature overhead by using RSA with ISO 9796-2: this is a signature algorithm with recovery which can be used to piggyback some data transport on the signature itself. If the underlying hash function has output size n bits, then the signature overhead is n+16 bits. There are constraints (the overhead is higher is the message is quite shorter than the RSA key) and there are known weaknesses which reduce the actual security level (with a 256-bit hash function, you would not get 128-bit security, rather something like 100-bit, which is already quite good). See this answer for details and pointers.
With ECDH and RSA/ISO-9796-2, we are down to 66 bytes of overhead. We can get lower by acknowledging that 128-bit security is, realistically, quite some overkill. Let's target 100-bit, which is still way beyond current technology (see that answer for more discussion on this). We can also use BLS signatures with an appropriately chosen elliptic curve. This can bring overhead down to 200 bits for ECDH, and another 200 bits for the signature. 400 bits is 50 bytes. Note that BLS verification is substantially more expensive than ECDSA signature verification (nothing serious for a PC, but this can be troublesome for embedded systems, in particular smartcards), and involves a non-trivial amount of non-trivial mathematics. And there is no industrial-level standard on BLS. Yet.
Getting lower than that looks challenging. There has been some work on multivariate quadratic equation systems, with a few proposal for signature schemes with short signatures (see HFE, Quartz and Sflash). Most were broken, using Shamir's relinearization. It is still believed that it is possible to get signatures shorter than 2n bits with a n-bit security level, but we have no candidate algorithm in which security we feel confident enough. Yet.