So, as promised, here're my thoughts about the main menu as well as some mockup artwork.
Let's start with the eye candy:
Absolutely most important part of the whole main menu: the intro screen! :D
*image removed*
Here's a variation of the current main menu screen, just a little more fancy and with actual menu items:
*image removed*
I was thinking it would be neat if the lines in the background would be scrolling or something like that, to make it less static. Also depends on if GM supports full alpha transparency...
And finally first shot at the character selection screen:
*image removed*
I'm not 100% about all that gradient slickness stylo things, but they're quick and cheap effects, so I just went for it.

Also I probably have to adjust some font issues, so not too many different font styles are used throughout the game. I guess we'll be using font maps, so I'll try to come up with as few different font styles/sizes that can be used throughout the game.
Concerning the options screen, can things like screen size be adjusted at runtime or would it be easier to make a sepparate menu that appears before actually launching the game (e.g. Spelunky)?
Also I think the Museum is a must-have part of the menu, since it could additionally act as a sort of help section. So besides showing the bio, original author and website of each character, also the movelist, explanation of each move and maybe even the corresponding sprite animation could be shown. I think it could help faltten the learning curve a lot, since the game only really becomes enjoyable, once you know the strengths and weaknesses of each character.
Also what about Credits? Should we make an extra menu entry, or will we have the credits in the readme only?
[EDIT]
Oh, and before I forget, here's how the interface elements of tug of war could look like:

[/EDIT]