@fgrieu gives an excellent answer.
One more option. Suppose you know that the plaintext has redundancy (due to some message formatting or something), and you know how to verify that its redundancy is correct (e.g., to check the formatting), but you don't know how to compress it or how to remove the redundancy.
Then a reasonable solution is the following:
Encrypt the message with a length-preserving encryption scheme such as CBC encryption with all-zeros IV and ciphertext stealing (I would not recommend using counter mode or a stream cipher).
Then, apply a public random permutation or a length-preserving all-or-nothing transform.
Finally, encrypt the result with the same length-preserving encryption scheme, but with a different independent key.
On the recipient side, you can undo this (decrypt, undo the permutation or all-or-nothing transform, decrypt), then check the formatting/redundancy. If the formatting/redundancy is valid, accept the message as valid and not tampered with.
(You might even be able to skip the first step, and just apply a public random permutation followed by encryption with CBC mode. But the above might be more robust.)
Even better would be to use a variable-length length-preserving block cipher (pseudorandom permutation), if you can find one. (For instance, some schemes for format-preserving encryption might be suitable.) But the above is a pragmatic engineering solution that should be good enough if you can't find a variable-length block cipher of the right length for your messages.
I'd expect this approach will provide as much integrity as is possible, given the assumptions I outlined. (I mean this only in an engineering/heuristic sense; it is not something I have proven mathematically.) It is also pretty easy to code up and apply. Therefore, this may be an attractive approach in practice.