The 3 Scenarios

Have you thought about putting encounters in the Crescent Mountain cave?  It would discourage exploration (which wouldn't be great), but it would also add a little more meat to Sabin's tale.  I don't recommend putting Serpent Trench enemies in there though, as making the Aspik/Anguiform Rages more accessible would give Gau some powerful stuff a little too early.  Sure, you can take a trip around to the Veldt right after the Battle @ Narshe, but a lot of players won't unless they're doing a challenge run.

Also, judging by the map, it looks like Terra's group will go right after the Ultros fight.  Do you plan on making that event change?

You are reading the map correctly. I decided to have Sabin and Edgar go through the Doma/Phantom Forest events, as it offered the most opportunities for character development. Terra and Banon get knocked off-course by the Ultros fight and go over Barren Falls. They start with the Rizopas battle, and wash up next to Gau's father's house, which is now actually on the Veldt. They meet Gau and try to rush back to Narshe.