Now, I agree that MP4 (AVC) is probably the better codec, compared to DivX (at least for most mobile devices), but I find it extremely annoying that on my standard N73 realmedia player, I can't skip forwards or backwards. (ps. I have never liked realplayer to begin with, even on pc...)
I have found a good (and free) no-mess-no-fuss solution to play my AVI movies on the N73.
1. Recompress your movies instantly with Mobiola Video Converter (freeware, their symbian video player is not). Just select your phone from the drop down list, move the quality slider bar (low to high) drag in the movie file and ta da!
2. Play the movie with the free DivX mobile player (don't need Mobiola player)
I haven't tested this with a full length movie, but 40min TV episodes came out great. If you like tweaking video settings till you tap every last bit of quality out of every bit, then stick with super + divX/real player.
Let me know if it works well for you too.