It's because they added Mewtwo, Roy, and additional costume/color slots. So you have additional portraits, CSPs, Battle portraits, etc. The only way to keep the file size from increasing is to reduce the quality of the images, since there are more of them now. However, if you look in menu -> common -> char_bust_tex, you will find about 3/4 of the victory screen textures, without the color bars but in a bit higher quality. If losing the color bars doesn't bother you, you can theoretically swap these textures. That would make the victory screen textures worse, and the character select screen textures better.
EDIT: Actually... upon trying to search for how large the common5.pac can be, I only found a couple of reports that it is a whopping 11.6 MB. I even downloaded what is supposedly a fresh clean copy straight from Brawl that is that size. The one included with PM is only 4.61 MB, so it seems like there would still be plenty of space. If I'm missing something here, someone please fill me in.
EDIT 2: Managed to find a CSP guide that says the common5.pac should not exceed 3.79 MB, which is more like I expected. I'm still unsure why a fresh file would be roughly 3 times that though.
EDIT 3: And upon even further investigation, it would SEEM that the 3.79 file size limit is not for the common5.pac itself, but rather the sc_selcharacter_en.pac inside of it. In any case the "fresh" common5.pac I got had one of that exact size. If this is indeed the case, PM3.0's sc_selcharacter_en.pac is 2.93 MB. That would give you a fair amount of room for improving the CSPs.