Everything you're looking for is in "sc_selmap_en", which is in "common5_en.pac". Open "common5_en.pac" up in BrawlBox and you'll see the following:
You want the BRRES file (or Resource File) labeled "MiscData[80]". Look in its Textures folder.
There's a lot here, and I mean a LOT! Don't worry, we'll do through the important ones one at a time.
The small icons you select on the Stage menu are called "MenSelmapIcon.##", obviously the hashes (a.k.a. number signs) stand for the ID numbers of the stage. To swap the image with one you want, right-click the file and select "Replace".
The name of the stage is also an image, known as "MenSelmapFrontStname.##". If you wish to make your own nameplate you'll have to create a black panel with white letters to make it display correctly. Easily doable in MS Paint, GIMP, Photoshop, or any other photo-editing program you can think of. Like before and all images to come, you can easily replace images you want by using "Replace", which can also be done by selecting the file (left-clicking) and hotkeying "Ctrl+R".
The Franchise icon like Fox's emblem displays next to nameplates are called "MenSelchrMark.##" Don't be thrown off by the fact there's nothing in the image, I did that to all mine because all my stages are skinned; many don't fit the shared Franchise Icons anymore and were just starting to look stupid.
The Game logos like "StarFox" appear above the nameplate, and are called "MenSelmapMark.##". Again, I've removed all of mine.
Then we have the large image that displays a picture of the stage. These are called "MenSelmapPrevbase.##".
There's a few other things you should know. First, of course, is SAVE!
There's another section where Stage information can apply, in "sc_selcharacter2_en". Open it and you'll see a single PAC (ARC) file labeled "MenuRule_en", which when opened only contains a single Resource File called "ModelData[0]". Open it and get into its textures folder.
This is where data stored in the rules menus are stored, which includes the Random Stage Switch. This is purely optional, but something I always do. Here there are only two images to change, the first being the "MenSelmapIcon.##" images. Some are the same as before, but many have slightly different ID numbers in here, like so:
We once was 15 but now we 14! Okay, getting back on track, the other one is a new one, "MenStageSwitch.##". Please tell me you know what this image is for...
Okay, fine! It's the image that displays at the bottom of the screen when turning off or on a stage in the Random Stage Switch. And below it is its name! In "MiscData[1]" you'll see all the names that display this way. Just find the original name and type in the name you want to replace it.
Finally there is one more thing that can and should be done: Uniform! "common5_en.pac" contains data that displayed when preparing to BRAWL or Special BRAWL, but "mu_menumain_en.pac" contains data that displays when in the main menus.
Right-click both "MenuRule_en" from "sc_selcharacter2_en" and "MiscData[80]" from "sc_selmap_en" and select "Export". Not "Export All", you'll get WAY more then you want.
Then open "mu_menumain_en.pac". There's quite a bit of data here too, but that's for another time. Just right-click "MiscData[0]" and select Replace, replace it with "MiscData[80].brres".
Then at the bottom of "mu_menumain_en.pac" you'll find another "MenuRule_en", Replace it with your new "MenuRule_en.pac".
We're done! Everything should now look just the way you want it to, and be uniform between menus!
