What algorithm would give the shortest ciphertext for very short plaintexts? I have to encrypt some very short messages (approx. 5 characters) and I would like the ciphertext to be as short as possible.  I am currently using AES but the initialization vector (IV) is making my minimum cipher text be 32 bytes, even for plaintext of 1 byte.

Can I do better than 32 bytes?
There is a technique called "format preserving encryption", which could be called an "arbitrary-size block cipher". This would allow to map your set of 5-character strings onto itself. Of course, this can't really get too secure, as it has still the limitations of ECB mode: encrypting the same string with the same key always gives the same ciphertext.

Your idea of using a mode with initialization vector helps, but bloats the message size, of course.

Since your effective message is sufficiently smaller than the block size, you could use a kind of "random padding" (similar to how it is used for asymmetric ciphers like RSA). For example, if your actual message is 5 bytes (and always this size, so we don't need to encode the size), you could add 8 random bytes and three zero bytes (as an integrity check), and pass the whole 16-byte-string to AES (as a block cipher, i.e. one-block-ECB).

On the decrypting side, you check that the last three decrypted bytes are zero, and then ignore the random bytes.

Now the ciphertext is different each time a different random value is used, independently of the actual plaintext, making it secure if the cipher is secure. (Of course, you should not use the same key for more than about $2^{32}$ messages.)

The protection against existential forgery is not that high, though, as three check bytes mean only 24 bit protection (in average 4 million tries necessary before a message is accepted). You can make this higher by using a smaller random part and bigger check part (meaning you should use the same key even less often).

If your protocol is serial, you can include a message number instead of a random value and check value, which also helps against replay attacks.