I think I've optimized the menus as far as I can - 909 frames from power on to the first plot screen.
Some things I've already noticed and/or need to remember:
1) Landing animations are bad. Avoid them whenever possible. If at all possible, don't jump.
2) There is no "takes damage to save time" in this game - when you get hit, you lose bottles, and you need to have so many bottles to exit a stage (in addition to whatever the stage has you hunting in the first place)
3) Lag Management is going to be a major thing.
Here's the Menus optimized as far as I can get them, plus a (basic) route through the first real level, "Gold Rush!". I know where most of my changes need to go (continuing on as opposed to waiting for enemies in at least two instances, maybe with the moth at the top of the ladder as well).