I'm convinced at this point that Elim Garak is the gayest slut in the history of Star Trek, and not just because Andy Robinson said so. Though the fact that Andy confirmed Garak's gaiety certainly helps my case, I have a few other exhibits to enter into evidence.
In 3.15-"Destiny", Gilora flirts with Chief O'Brien by being argumentative and insulting. Garak and Dukat do pretty much nothing but argue and insult each other whenever they have any screen time. The only time they don't is when Garak walks into the room with his new boyfriend in 2.05-"Cardassians" and grins smugly at Dukat, who says nothing but gives him an icy glare as he exits. I submit that Garak and Dukat are ex-husbands; Papa makes some reference to "that business with the arms merchants" when Garak brings him up in 3.21-"The Die is Cast", suggesting that Garak didn't want him to know he not only married, but divorced a common glinn from the Bajoran occupation forces and just made something up. Why did they split up? Who knows. Maybe something having to do with someone's career? Or maybe Garak was sleeping around. I'll unpack that in a second. But Garak seems to take some kind of pleasure at the idea of assassinating Dukat.
This opens up a new level to Cardassian sexuality that I think needs to be explored in greater depth; ex-lovers patch things up by attempting to kill each other. Not much is known about Cardassian belief in an afterlife, but if they're anything like other humanoid species, they probably have one. It's feasible that Cardassians kill their exes so they can exert dominance over them for eternity or something to that effect.
Now, in relation to Garak sleeping around. During the occupation, Garak was basically James Bond, so bearing all this in mind, I firmly believe that he was also seeing Gul Toran (2.18-"Profit and Loss") and Entek (3.05-"Second Skin"). When Toran walks into his shop, the very first thing they do is insult each other; he begins arguing with Entek the moment he walks into the room. Certainly, while killing them ended the threat du jour, it was a secondary effect to Garak getting off on it.
The fact that he brought a phaser with him to his first date with Tora Ziyal points to that kind of foreplay killing, but it took the wind out of his sails a bit when she didn't have any plans to kill him. He probably failed to take into account the fact that she wasn't really accustomed to Cardassian mating rituals and ended up getting turned off, since he never initiates any romantic contact with her, to say nothing of the fact that they hardly ever argue. To him, she's just a friend who kisses him occasionally. He spent the rest of her life trying to figure out why she thought she loved him romantically since she never exhibited any of the traditional signs.
Since Garak initiated first contact procedures with Dr. Bashir, we can reasonably assume that he looked up human culture on the computer and arrived at the literary trope of "tall, dark, and mysterious", and so presented himself to Bashir as that kind of figure.
I started this out calling Garak gay. However, the thing we shouldn't overlook is that Cardassians aren't as puritanical about sexuality as humans. I'm not dismissing the fact that he probably did think Ziyal was cute. The fact is; and Andy even said this; Garak saw an attractive person and introduced himself immediately. The fact this person was Julian Bashir makes no difference. If it had been Julie Bashir instead, he still would have. Garak might be what we humans call "pansexual", but he's just a garden-variety Cardassian.
I think Garak's marriage ended because it turned out Dukat had a raging Bajoran fetish, actually.