For me, create the menu arrives near from the end of the development. You should first have a strong protocol, so, even a poor UI is fine, until the gameplay itself is fun.
For my part, I usually start with the character’s skeleton and the animations, if you develop a game focus on a main character (of course). And then, I try to create the gameplay in itself with all the interactions with objects and the world, but I don’t polish it for now. I just want to have something which works. And then, comes level design…
But it’s just my way of working, when I want to develop a game’s prototype/experience alone.