It all depends how they're going to handle NX launch and what NX actually is.
I am still of the belief that NX is the architecture/OS across multiple platforms which may share games if the developers wish, but does not have to, due to Iwata essentially saying that. So, my theory is NX Handheld 2016, NX Console 2017.
As such, Mario is far more likely for NX Handheld launch, whereas Zelda will be Wii U in 2016 still, or launch of NX Console in 2017