Try twofish.
I looked at the C code to implement it. Just guessing from my short peek at it, but the code itself might fill the whole ATmega168 and more. I will see what parts really need to be there. It would be kinda fun to make an "Ardufish device," huh?