Take a look at the specification for transaction messages, particularly the sample transaction: https://en.bitcoin.it/wiki/Protocol_specification#tx
The best way to minimize transaction size is to minimize the number of inputs. Avoid accumulating "dust" balances of very tiny amounts. This is why mining pools have minimum payouts.
Vanity addresses are still the full 20 bytes. Even if you use a firstbits address, you have to look up the full address before using it.
[Moved the answer from the comment below to here:
You don't get a transaction size saving from using firstbits, because it is not legal in the protocol and you will have to use the full address anyway.]