MC will do everything you describe. In fact, it is one of the only programs I know of that will do exactly what you described. There have been several posts regarding the use of smartlists for working with an iPod and I'm sure they'll be relevant.
You can define playlists manually or by using rules for the categories you described. For example, I have a playlist called World Beat Master that includes all music where the genre=African, Arabic, Brazilian, etc.
Then you can define a smartlist based on any other playlist, specifying a modifier for random sorting and for limiting it to the memory size of your player. To continue with my example, I then make a smartlist called World Beat where the definition is playlist=World Beat Master, sorting=random, limit=1000 megabytes.
I usually add another parameter, to exclude songs I've heard within the past month. That way each sync gives me new tunes.
Once you've built these lists (which is even simpler than it sounds) it's just plug & play. Every sync will give you a fresh batch of tunes. Depending on how you've defined your smartlists, new music will be categorized appropriately without any further intervention from you.
I'm betting that MC will directly support any player that turns up as a storage device. However, you can always select any playlist and use the Move/Copy command to copy the files in the playlist to any other location.