I was describing pima's encryption to someone, and they mentioned that I might consider using b-crypt or s-crypt to generate the AES password from the plaintext password provided by the user, since the plaintext password is likely to be relatively small.
So I tested b-crypt with "12 rounds" for the hardness parameter, which is just a number I've seen thrown around the internet. This gives us:
MacBook Air: 1.798 seconds
Droid Razr Max HD: 10.379 seconds
I also tested s-crypt with "2^14" as the hardness parameter, which I've read is appropriate for interactive logins, whereas "2^20" is appropriate for file encryption, which is what I want, but "2^20" fails to run at all:
MacBook: 0.835 seconds
Droid: 2.379 seconds
Hm.. I think I'll go with s-crypt for now. It will at least be better than what I've got, and not too slow on the phone..