I was just grabbing screenshots from the Brawl Vault mod vault and clone stamping out the fighters. 86x86 is a good size, but you want JPEG format. Also, I've been exporting the image at low quality setting as well (if you're like me and have your Photoshop default set to 12 High Quality).
I just started using the Stage Manager about 30 minutes ago, now everything is super simple.
http://www.lakora.us/brawl/stagemanager/
Play around with it some, you'll get the hang of it pretty quickly.
EDIT: Btw, after finding the font and making stage names the hard way last night, I found this morning that the stage manager will do it SUPER DUPER EASILY, eliminating the need for downloading the font entirely. It's good to have though, I guess. I'll just have to find something to do with it.