Re-encoding usually sounds terrible, so it's better to recompress the original. If you don't have the original or you need to recompress your paid downloads (which are already compressed), it's better to firstexpand the files to wave files, and then use a codec on the wave files. That's manslaughter and not murder, which would result if you went straight from 320kbps downward or (worse) converted to another format.
For low bitrate files, I find wma and ogg far superior to MP3. A 64kbps WMA is considered equivalent to a 128 kbps MP3, which should be enough for portable listening. In the time I could listen to music on the move, I used 96 kbps OGG files, and those worked fine with my Altec in-ears.
As to software, there are tons, but the only ones I'd consider are dbPoweramp + its DLC codec packs and the built in converters in CDex, both capable of all you want to do with your files. I use Winamp's auto-tagger to tag the converted files, which works maybe 80% of the time (dependant on a public tags database).