AMD's long term solution was a major overhaul of their archectecture called Polaris, to improve what they call Performance per Watt. With the release of the desktop AMD RX480 and RX470, there's no doubt that AMD have made up a lot of ground on Nvidia, yet a noticable gap still exists when you compare the latest generation of both companies.
This isn't likely to deter Apple in choosing AMD as their GPU supplier again though, as the preferential pricing from AMD sweetens and sourness from not having the best avalilable.
There's also the potential of custom APUs with the release of Zen next year, with a big CPU and GPU packaged into one chip like the Xbox One and PS4, but that's another topic entirely.
What will Apple pick
The problem for Apple, is the new mobile Polaris GPUs aren't very fast. The mobile version of the RX480 is based on a cut down chip with half of almost everything, making it much slower than the outgoing R9 M395X.
Apple will need to use the desktop AMD GPUs again to even maintain performance with the previous generation, let alone improve it.
This year is the first time in a while where they can use desktop AMD GPUs. The RX470 is rated at 120W TDP, which compares with the current M395X's 125W TDP. If Apple can put a RX470 into the iMac, that will offer a 50% performance increase over the M395X for roughly the same power usage.
Will Apple use a RX470? I hope so, although they can get away with a slower RX460 and still improve over the previous generation, the iMac can handle the RX470 and it would be a shame if it wasn't an option at least.
The base GPU would then be the RX480M, which is comparable to the outgoing M380, and I'd imagine the RX460 or similar as the mid range.
This does pose a problem with branding, with the RX460 and RX470 being much faster than the bottom of the range RX480M. So like the Mac Pro I expect AMD to allow Apple to have their own model names, perhaps W460, W470, and W480:
Good: AMD RX480M 2GB (W460)
Better: AMD RX460 4GB (W470)
Best: AMD RX470 8GB (W480)