You forgot Jake and Kira. That
would have been...interesting (mostly for the...added dimension of the relationship between Kira and Ben). But I think Jake is probably too exciting for Kira.
Jake/Ezri would have been the best option if Ezri had to hook up with someone in the cast (Boday would have been funny). Certainly better than the obvious Bashir (who should have kept up with Sarina, long-distance - that was far and away Bashir's best romance), or the gross thing with Worf. Plus, it would have given Jake something
to do last season.
I actually voted for Quark + Grilka. I liked them together. They liked themselves together. It would have created a more interesting dynamic between Quark and Worf than "keep your Ferengi eyes off my girlfriend/wife." And Grilka would NOT have allowed Quark to get a sex change.