What's the point of having it on the loading page? By that time, it's too late and useless. It has to be on the same screen as you choose the map.
Options:
Split the new game screen into two parts, for example, start by choosing the players and their factions, then click continue, and choose the game's settings, like the map (since we previously chose the number of players, we can automatically filter out maps that use less players than we have chosen), fog of war, etc etc. This gives optimal space, but probably more difficult to program.
Use scroll boxes to bunch some of the controls together in one small space, having to scroll down in that space to access all options. This is far more cramped, and not necessarily any easier to program than splitting the screen.
Stuff it in. This is the simplest option, but then things become more crowded than ever. I think controls should be spaced out a bit, lest the new player be overwhelmed by all the options.