How many different formats can a public address take? I'm creating an offline index to report off of the block chain.  I plan on indexing each transaction based on the address displayed in the TX.

Are all addresses Base58?   I believe I also read about a compact address and an address type that was used in the beginning of the blockchain before Satoshi knew of/implemented address compression using Base58.
I believe that the earlier format that you are referring to is the Hash160 which is formed by taking the sha256 of the public key followed by taking the ripemd160 of the result:


Hash160 = ripemd160(sha256(pubkey))


Further, what we usually refer to as a Bitcoin address is formed by first concatenating the Hash160 with four checksum bytes (to make it extremely unlikely that you can type the wrong address into a bitcoin client by accident). Then, a network identifier (0x00 for main network) is prepended and the string is base58 encoded:


address = base58(0x00 + Hash160 + checksum)


As you can see these two formats can easily be converted from one to the other. In addition the public key can be encoded either compressed or uncompressed. This results in two different addresses. However, since you can obtain the public key from neither the Hash160 nor the base58 address it is not possible to convert an address of an uncompressed public key to the address corresponding to the compressed public key, and vice versa.