What att stated is pretty much spot on.

Something else to think about if you are going to re-encode them you can make it into another container if mkv isn't supported.

"Most" encode applications will also rip the subs from anime as well.

For the other part you asked about I would try something like the following;
Video Rate - 900kbps @25FPS variable
Audio Rate - 192kbps @44100
MPG4 encode or H264

This is about 2 steps up from my Nokia N97 encode settings. I don't have a N900 but I would imagine these settings would play very crisp while giving out no distortion or artifact effects.

Again I don't have a N900 so I can't test but I am going to do the same thing with mine, download my Anime into it for on the go watching.