SteveC's solution is very elegant. If you didn't want to have to boot up different libraries in iTunes however, you could convert the files but store them in the same library and set up a playlist or playlists using only the lossy files and update the iPod with these playlists. On the downside, you will have duplicate files in your single library.
An alternative approach altogether might be to stick with ALAC and set up a smart playlist in iTunes that is limited to 16Gb. If you based the 'limit to 16Gb' logic on when the file was last played for instance, you wouldn't be constantly repeating the same songs (provided you sync the iPod regularly)
Finally, learn from my mistakes and don't be tempted to rip directly to mp3 - I did that a few years ago and now I'm redoing them all in ALAC. It's twice as tedious second time round...