If you're including another faction, Windwalker will work best with new players.
High Priests are a must include. As for maps/GOOs, probably just try the one you fancy.
I'd say High Priests too. We always find that WW does disproportionally well with new players as they tend to ignore him (Sleeper too sometimes) but is probably easier to play than Sleeper or Opener.
Primeval Earth is a fun map as everyone ends up with lots of power. Yuggoth is good but you need to be able to predict when the Watcher is going to come out and what might happen. Dreamlands/Library are a bit tricky due to the separated maps.