OK, just to close the loop on this, in case someone in the future have the same problem.
I went the Citroen dealer and they allegedly 'reinstalled' the software on the unit (I suppose the process is more invovled / aggressive than just usual upgrade from USB stick - but what was done here exactly is hard to say).
Afterwards, Android Auto appeared on my NAC - all works great now.
I suspect that my NAC was the very first version of Wave 2.1 (from 2016) and they did not have AA at the release (which would explain why the feature is not mentioned in the paper manual I got with the car at all - while CarPlay / Mirrorlink is). Subsequent upgrade via USB (to a release containing AA) would not enable AA - because, to be honest, traditional carmakers will never give you any new features in the updates, especially for 'free' (and there is a problem of rewrting manuals, support for these, confusing the users with new icons and options, etc).
Likely a more invovled reinstall (done by the dealer) would wipe / revert to factory default 'features flags' or so in the software and activate standard functionalities for the given NAC version, including AA (It also enabled 'Connected Apps' feature for me, but this one seems to be pretty much useles). Or something like this - but I think this theory sounds more less plausble
Thank you @GiveMeABreak for all the input and help here!