Perhaps for those who are slightly less noob, my own favorite is Handbrake. Handbrake is really quite powerful, but it doesn't require too many steps to coax it into converting a video into exactly what your N900 desires. In fact, using this, there's no need (or point) to loading extra decoders. The major steps are these:

1) Open your source video in Handbrake.
2) Select "H.264" as your video codec.
3) Under the "Advanced" tab,
3.1) set "Maximum B-frames" to 0, and
3.2) turn off "CABAC Entropy Coding", "8x8 Transform", and "Weighted P-Frames".

You are now set to convert the video into an H.264 "baseline profile".

For the rest, I normally do the following:

4) For high-definition video, I only reduce the size enough to just fit it into the 800x480 resolution of the phone. (800x448 is the perfect choice for modern 16:9 widescreen video, to leave the aspect ratio intact.)
5) Choose either MP4 or MKV for your container format, both work fine.
6) I leave the frame rate at the same rate as the source video, this usually works for me.
7) Not being an audiophile myself, I usually let Handbrake do its default effort on the audio track...

The only real problem I have is with subtitles. As Media Player doesn't handle them (at least not without serious help), I normally just let Handbrake "burn" them into the video itself.

Media Player on the N900 has no trouble playing H.264 baseline profile video at 800x480 resolution, with decent frame rates, with decent audio, no need to load any extra packages, no need to overclock, no need to do anything. It just works.