The single most important thing is to avoid putting anything in any data (non-header) cell of the new column: no data, no formulas, nothing! The occurrence of anything in a data cell instantly brings the column into existence and will cause problems for any version of the app that isn't expecting a column there. If you find something in the column unintentionally, select the column and clear it.
To add a new column:
1) Add the new column to the left of all existing columns. Do not insert the new column between existing columns. Do not add any data or spreadsheet formulas in the new column; only add the header.
2) Regenerate the column structure for the table. Perform only minimal configuration of the new column, such as disabling Show? to avoid confusing the users. Do not add any configuration that might give or allow the column a value: no App formula, no Initial value, no Spreadsheet formula, disable Editable?.
3) All users must resync the app to get the new column before you perform any further configuration or use of the new column. So long as you don't add any data to the new spreadsheet column, earlier app versions should entirely ignore it.
4) After all users have resynced and have the latest version of the app, you may configure and begin using the new column. There is no way to force a resync, the users themselves must trigger it. There is no way to check whether all users have updated. It's on you to notify them and to impress upon them the importance.
You may add multiple columns at once if needed.