[2020] 4 players! Which map?

In my opinion, as you've never played before, I would suggest Navezgane- It's the only handcrafted map, isn't too large, has good biome layout, distinct locations, and a bit more...It's only defeating factor is that the map as a whole is always essentially the same. But for new players that's not really an issue.

If you generate a random map, you have the option of generating it at 4K or 8K size. Navezgane is in between, at about 6K. Maps take a long time to generate, so you could also go with one of the pregen maps.