I'm not at home right now so I can't check details on exact settings, but I'll try to hit the most important stuff...
Your best bet is to convert down to h.264 baseline with aac 2-channel audio in an mp4/m4v container and play it in Rockplayer using hardware decoding. (The Xoom is my first android device so there are likely other players that would work as well, but Rockplayer is the first one I found that worked.)
Going from memory the easiest way to get to the appropriate settings is to just select the Normal profile preset to start with, then on the advanced settings make sure you have:
Reference frames: 2
B frames: 0
CABAC: no
8x8: no
Weighted p-frames:no
Picture:
shouldn't have to change anything
Video Filters:
This depends on the source material. I guess leave it alone if you don't know.
Video:
For the video settings, it's largely a matter of personal taste, I suppose. For the sake of providing example settings, I'll assume your source is an average dvd.
2-pass encoding with turbo first pass
avg. bitrate: 1200-1500 (1200 is probably fine on a small display and/or if you aren't picky, but I consider that to be the bare minimum for dvd content...others may disagree)
There are plenty of other settings that will "work", but this will consistently produce reasonably sized files that should look quite nice on the Xoom's display.
Audio:
AAC: Pro Logic II, defaults should be fine otherwise
Subtitles:
Probably safest to burn them in if you need them for the movie you are converting. I haven't dealt with anything on the Xoom that has subs yet.
As I said, this was all from memory, but I think I got the important stuff right
If your source is not a dvd, you may need to change some things. Let me know if there are any questions.