Let's say 2+ people are entering sales orders all at once, and NetSuite pre-populates the auto-generated sales order number with the same number. Since one user will save her order first and claim said sales order number, the other user will then go to save her order, and have to click through a few prompts in order to agree to saving the sales order as a new number. Is there anyway to avoid all of that and just have netsuite know, on save, to replace the sales order number with the next available?

Uncheck the Allow Override for auto-generated numbers. Check out "Using Auto-Generated Numbering for Transactions" SA ID: 9071. That way numbers generate when transactions are saved, not when started.