"Downsizing" an mp3 is what we call transcoding, and it's bad. An mp3 (or the better ogg vorbis) works (basically) by discarding parts of the audio that you won't hear. Doing that will discard parts of the mp3 that already has a bunch of parts discarded and this makes it sound bad.
I do something like what you're looking for, but it's all through a bunch of custom scripts and crap that I made. I buy flac, encode that to ogg (which sounds better than mp3s at lower bitrates), those oggs get synced to my phone, then later I organize those oggs to my collection.
I think you'll have to either accept these large mp3s or start a lossless collection.