I'm going to argue SW, followed by the completion of a half crescent back toward our Capital. (By the way, weren't we going to name it Three Immortals?) After that, the warrior should head southward. This will give us an idea of how large this landmass is we are on. He can zig back and forth or do whatever we deem best at the time.
The second warrior can pick up the job of scouting the immediate area by finishing off the crescent.
I'm not to worried about defending our cities in the early game. The size of the map and low number of teams means there is more risk from a barb event (which wouldn't happen during the warrior phase) then from an attack by another team.