Actually, the iPod Shuffle (only) has an option that transcodes the songs on the fly to 128kbps during the transfer (this of course makes the transfer sllllooooowwww).
If your songs are already in a compressed format, no matter the bitrate, reconverting them will lose quality and not save you any real appreciable amounts of space. If they're lossless, of course, that's another story.