Messages in SQLCMD script output are not in order
PRINT output can be buffered.  A great way around this is to use RAISERROR (@msg, 0, 1) WITH NOWAIT; instead.

For example:

DECLARE @msg nvarchar(1000);

SET @msg = 'Do the first thing';
RAISERROR (@msg, 0, 1) WITH NOWAIT;

SET @msg = 'Do the second thing';
RAISERROR (@msg, 0, 1) WITH NOWAIT;

SET @msg = 'Do the third thing';
RAISERROR (@msg, 0, 1) WITH NOWAIT;