A resposta: link :
Apparently the mysql-server installation on 16.04 (or any 5.7 installation?) allows root access not through password, but through the auth_socket plugin. Running sudo mysql -u root (n.b. w/o a password) will give you mysql console whereas running the command as non-root prompts you for a password.
It would seem that changing the password doesn't make much of a difference since the auth backend doesn't even check for a password.
Para desabilitar este plugin auth_socket, no prompt do mysql faça
update mysql.user set plugin=null where user='root';
flush privileges;
Isso faz com que o MariaDB também peça uma senha para o root [Linux].
Obrigado jesse-b e derobert pela discussão profunda e suas respostas.