MediamonkeyMediamonkey seems to cover most of my needs.
The free version handles 1 and 3
It allows me to Sync a random subset of files up to the device capacity, and let me leave a certain amount of space free.
The paid version also does conversion based off rules so does 2. Its standalone (though not portable), and dosen't rely on anything else.
As a bonus, it seems to be a competent music player, even doing WASAPI