Which block cipher modes of operation allow a predictable IV? Recently I found out that in the modes CBC and PCBC the IV may be passed in cleartext but never must be predictable. However for this part of my app I rather have the IV be predictable and unique (i.e. generated from other data known to the "receiver" and also the adversary, and not stored/transmitted with the ciphertext) rather than random.

What options do I have as a cipher mode? How do I choose between them? Which is the main difference between OFB and CFB?
The short answer for the mode: use EAX.

There are several reasons why EAX is Good, but, in particular:


It includes integrity check, which is a must have (yes, really; defense against active attackers is often overlooked, and this is equally often deadly).
It needs a unique IV (a nonce) but tolerates predictable nonces.


As for OFB and CFB, see the Wikipedia page which has nice schematics. However, since neither does any kind of integrity checks, you would have to add some kind of HMAC, so choosing a nice integrated mode like EAX is simpler (and simplicity is good for security).



If for some reason you really cannot use EAX (or another similar mode), you can survive CBC by generating unpredictable IV the following way: use your source of "unique, predictable IV" to generate block-sized values, and encrypt each value with the block cipher, using a distinct secret key (which you do not have to share with anybody else). This is like using the block cipher as a PRNG. You still need a bit of randomness at some point (when you generate that extra key) but not as much as previously.