I'm not certain what you're expecting in terms of quality given the portable medium you're trying it on. Limitations and Portability go hand in hand, so given what we have to work with, I think that a level of adequate quality can be achieved, even for the most stringent purveyors of quality.
Since you think higher bitrates are sexy, have a go with
BetaPlayer, it handles high bitrate avi's with relative ease. I would recommend encoding in Xvid with B-Frames on, the level of quality you can retain is very nice. Additionally, you should find a link on the same page for encoding software, PocketDivxEncoder, which outputs avi's formatted specifically for the PPC.
I would be interested to see what your results are using a media player other than WMP.