Ciphertext stealing doesn't bring you any security benefits, although – if you're hell-bound on using CBC mode – it could avoid padding oracle attacks. Otherwise it is just a way to avoid padding the plaintext and therefore increasing the ciphertext size in CBC mode.
Ciphertext stealing is independent of the block cipher used. So you could use it with 3DES, Blowfish or indeed AES in CBC mode. It's also available in ECB mode but ECB mode itself is not considered secure.
Blowfish is not an interesting alternative to AES. Even Bruce Schneider, the principal engineer of the cipher, recommends against using Blowfish. Although it hasn't been broken its 64 bit block size makes it an uncomfortable fit to most modern modes of operation, especially those that use CTR underneath.
When using messaging you should probably have a look at AES/GCM or another mode of authenticated encryption. Ciphertext stealing is not that interesting, just use something based on counter mode such as GCM. CTR and most other modes of operation do not require padding nor ciphertext stealing.
Choice of the block cipher isn't that important; creating a secure protocol is much harder. Then you can drop in any modern, secure block cipher you want. To play it safe, just use AES.