Sounds like you might be after deterministic authenticated encryption. Check out SIV mode. This mode doesn't use an IV at all (though it does generate one internally, outside of the attacker's control). Being deterministic, it leaks equality of (header, plaintext) pairs.
The basic idea is to put the (header, plaintext) pair through a PRF, such as HMAC, and use the result as an IV for, e.g., CTR mode. After decryption, you check authenticity by checking to see if you can reproduce the IV's value.
If you want to be able to stream plaintexts, look into "Online ciphers from Tweakable Blockciphers". As you anticipate, these schemes leak shared prefixes but are otherwise secure. But note that this latter paper does not consider authentication, and generic techniques that assume standard IND-CPA security may not work. See "On-Line Ciphers and the Hash-CBC Constructions" for how to get AE in this context.