Yeah the N900 may not have enough processing power.

Don't waste your time with the built-in video player, install Mplayer/KMPlayer.

I used mencoder to convert videos (better do this on a desktop). This is a script I use to convert a 16:9 video with MP3 audio:

Of course if the video is 4:3 you might want to go with 320x240 resolution - it still looks pretty sharp. The compression artifacts are sometimes noticeable though, you could probably increase the bitrate quite a bit before it would bog down the CPU.