It's hardly a case of either "some form of projecting power into other States" or "a bigger, 'smarter' Interpol/FBI/CIA/NSA", is it?
More like you can't have one without the other, isn't it? And it is precisely that "some form of projecting power into other States" that creates the anger, no? At least the way that power has been projected over the last 50 years or so.
It seems to me that the last major challenge to "some form of projecting power into other States", namely Indochina, brought about some roll-back, at least the FOIA. The present "projecting power into other States" has come with enhancements to "internal security" in the name of "homeland defence", hasn't it? That said, dangers and all, better an international police projecting power into _all_ states (rather than some states projecting power into other states) -- let's have the ICC, etc. and let's depend upon enlarged democratic spaces and state nationalisms, with all their flaws, to act as the check and balance on that international police...
You want a virtual 100% assurance that those who feel wronged by US power won't attempt any attacks, then you'll need to bite the bullet and countenance preventive detentions without trial, rollbacks on civil liberties, etc. and swallow the consequences of that. Else it's having to live with the insecurity, which is probably at a very much lower level than the horror of Sep 11 might have conveyed; the risks are probably considerably lower than that you might die of one or another cancer! While the attempt to reach for that 100% would produce other, and more tangible, insecurities, especially if you have activist aspirations.
By the way, it really doesn't have to come from outside, as implied by "attacks on the US", does it? The Oklahoma City bombing was homegrown, the current pipe bombs appear to be homegrown, the anthrax attacks were homegrown. There's enough 'anger' in your own backyard, fueled by the state of siege (by 'liberals') preachings of the ultra-right, and all it takes is for someone or another to act it out.
But if you really want to try for 100%, then do what Dr Mahathir has been crowing about: "they used to condemn us, but now they're doing exactly what we've been doing", ie. an inherited colonial law that allows for preventive detention without trial, of up to 2 years at a time, renewable indefinitely, under which we have had people who went in at the age of 27 and came out at the age of 42. And oh, yes, the satisfaction that Washington has with Malaysia's (and Singapore's) arrest of alleged al-Qaeda operatives -- all these arrests have been under preventive detention: no more condemnations of 'undemocratic', 'draconian', etc. Still even then, you'd be unable to reach 100%.
But really -- if Washington were to behave differently, if you didn't have the most senior Republican advocating ethnic cleansing (and no huge cries of horror in response), you might just be surprised at how well regarded Americans and the US generally is, even in Muslim circles. Religious ultra-conservatives outside the US dislike much the same things that ultra-conservatives within the US do -- they actually will read the stuff that comes out in townhall.com, worldnetnews daily, etc., and they will nod their head when the jerry falwell's talk about the satanic activities of americans. But they aren't going to be journeying to the US to go bomb something or other; more like go there for a holiday, to disneyworld, etc. Rest assured -- American cultural hegemony is amazingly alive and well and there was considerably much less schadenfreude than your TV networks might have led you to believe. One can only be grateful that the American Christian Right is so blind-sided that they can't see that if they were to adopt slightly different political positions, their natural allies would be the Muslim ultra-conservatives -- now that would be terror on a world scale!