It might have been a bit predictable. Safe... I don't know about that. In some ways, a relationship between a solid and a Changeling, due to the fundamental biological and psychological differences between the species, is far weirder and more 'out there' than a relationship between two humanoids could ever be, even if there is a long and painful history of animosity and hatred between them both on a personal level and between those humanoid species. I thought it was great that the show did not gloss over those issues but confronted them in "Chimera", and that it eventually did not go the romantic 'love conquers all' route, and made them part ways instead of making them live happily ever after. I don't think that was predictable. For the record, Nana Visitor was not in favor of that storyline either - she said she would have preferred Odo and Kira to remain just friends, because she thought the series should show that a woman and a man can be just friends, and also she didn't want them to become the happy couple of the station; and neither she nor Rene Auberjonois liked the episode "His Way" in which their characters finally became a couple. But she later said that she ended up liking the way the relationship was dealt with later on, and that she was glad they did not get the happy ending.
I am curious, mysticgeek, since you think a Kira/Dukat romance would be a good storyline, how you imagine it could have happened, and how would the relationship have worked? If you were a writer on the show, how would you write it? I think that, for me to find any K/D hookup remotely believable, one would have to come up with a scenario that would involve some very unusual circumstances and extreme emotional states for Kira. And then, if it did happen in the first place, I think Kira would hate herself for it; and even if she did not, there's still this problem: Dukat would not just magically turn into a good guy (the romantic rescue fantasy that a bad man only needs 'the love of a good woman' to reform is just that, a romantic fantasy) or into a person capable of having a relationship without trying to make the other person submit and share his delusions about him being a great guy who has done nothing wrong to Bajor or anyone - and you must realize Kira would not do that and could not remain silent about what she thought of his actions. Any hypothetical hookup between those two would have to be very short-lived and would end very badly. They'd be far more likely to kill each other than to 'live happily ever after'.
And, everything else aside - do you really believe that such a relationship, even if it had somehow worked, would help bring peace between Bajor and Cardassia? How and why would any hater change their mind on account of that? Say, imagine that there is story all over Bajoran and Cardassian version of tabloids and other media about a hookup between Gul Dukat, the former Prefect of Bajor and commander of Terok Nor, and Major/Colonel Kira Nerys of Bajoran Militia, former distinguished member of the Bajoran Resistance. What would, realistically, be the reactions? I can imagine shock, disbelief, curiosity, a lot of snickering and many judgmental and very non-complimentary comments (out of those Cardassians who would care about what Dukat does in his private life, the majority would probably say something like 'his thing for Bajoran whores has always been his undoing'; and as for Bajorans - I don't even want to think about what Bajorans would be saying about her, suffice to say they would lose any respect for her). But I can't picture many people changing their minds and saying: "Oh, you know, this makes me think that maybe those Cardies/Bajorans are nicer people than I thought." (Unless it was said with a sarcastic wink and a nudge nudge.)
I agree, but like Nerys, I would say that it did serve as such a symbol. (I cried buckets at the end of that episode, too...)
Let's see, Dukat would be the bad boy that the heroine hates at first and is always bickering with but actually sort of likes him; Odo would be the likable geeky best friend who is secretly in love with the heroine; and Shakaar - the generic jock boyfriend that the audience is rooting against and who is destined to get dumped before the end of the movie. 
I guess from that perspective, all that is missing is Kira and Dukat ending up as a happy couple after she learns that he's not that bad after all. Then Temis The Vorta would be completely justified in her view that Trek relationships are written on a juvenile level. 
