Two solutions:
1) I believe that syncing with Windows Media Player allows you to also sync playlists, which I'm pretty sure you can arrange by genre, or
2) if you want to stay away from WMP,
you might be able to use this. It's designed for iriver mp3 players, but should work with any UMS device (like a CF/SD card reader). It builds a database file (which was used by the mp3 player) and also can be configured to make "auto-playlists" by genre, etc. A really useful program for my old H320, not sure about how good it would be for a ppc, however.