I'll say the War Arc Gaara takes this one, not the Rescue Kazekage Arc Gaara.. I just don't think Konan, the God's Angel, should be underestimated..
The only things between Konan and Deidara you might compare r their bombs.. Other than their bombs, they r different type of fighters.
She made dozens of explosive paper clones of herself as seen in her battle against the Aburame Clan. She is made of paper so naturally, her weakness would be water but she would use her own weakness as her advantage, like being able to go through fire/explosions. She handled the insects with ease, I would think sand wouldn't be much more difficult than the bugs. (bugs burrow sand, but gaaras sand can change dense so the sand is better) She doesn't blabber and stays collected, for some reason, she seems to be tactically smart, she is also highly evasive..
Although, Deidara may be a bit evasive as seen with dodging Kakashi's developing Kamui. I think Deidara's ego and being one of the youngest Akatsuki member (experience speaking too) made Deidara less of a challenge for Gaara. If Deidara thought like Konan did, he would've posed a much bigger threat especially with his much more powerful C2,3,4 bombs.
Which is why I think Konan do have a chance of taking Gaara on, but with the new Gold Dust technique Gaara just got, Gaara gets this one.