Bashir as leader of S31 is something that could work - he's augmented, intelligent, has experience. And he's not evil. I think that some of the dislike of S31 may come from the same place as the resistance to Starfleet being the de-facto military - some think armed forces are almost by definition bad guys, and the same may be true of obscure intelligence/secret service agencies like S31 and its real world inspiration. However, if 24th century humans are supposed to be enlightened, why would S31 be more evil than Starfleet (the de-facto military) itself? Sure, they may have the equivalent of a badmiral, but there is potential.
An S31 show could be like Mission Impossible in space, with a well oiled team using futuristic gadgets to accomplish feats. Or it could also be a political thriller as S31 would presumably want to protect the Federation and further its political, economic, military (etc) position.
So what would the difference be with a show about regular Starfleet Intelligence? Well, because that institution has the reputation of being incompetent (they are being infiltrated or allowing infiltrations, coups etc of upper echelons of Starfleet all the time, with a bit of hyperbole) and also of playing by the rules (respecting treaties etc).
What would the practical difference be? Take the phase cloak on the Pegasus. Starfleet Intelligence would agree with Picard (and Riker) and arrest that admiral for breaking the treaty about cloaking devices (because they are good guys who stick to the rules). S31 would probably help (or even recruit) the admiral and help him hide the cloak, for their use and for possible use by Starfleet later should it be warranted/needed. Because they are the sinister spy agency and they look at results first (and Starfleet can deny them).
Same goes for what Sisko did: Garak did his dirty work, but S31 would also have done something similar if they felt it was needed to preserve the Federation (as did Sisko). Starfleet Intelligence would probably never do such a thing, unless their Romulan infiltrator/commander (of the moment) actually felt it would be in the best interests of Romulus in the end (which it probably was if they don't fancy being a client state of the Dominion, at best).