I've found that for MP3s the best thing to do is to look for files that are 192 kb/s... Since most people download 128 kb/s songs, those are the ones that the RIAA f***ed up the most. I haven't found ANY problems with MP3s at 192. Try it.
That's not mentioning the fact that 192s have better sound quality anyway.
As for the differently sized files, some things are ripped differently then others which results in different sizes. It also comes from being (for mp3s) a smaller or larger bitrate/second, and (for programs) they're either zipped or rarred or something of the sort.