What is it about Machiavelli's ideas that so horrifies readers and generates such a wide disparity of interpretations?

It is not the idea that crime pays. That one has been explored time and again by philosophers and theologians who have "cast enough light on political realities to shock the credulous and naive out of uncritical idealism (2)." 

My guess: Just as Darwin unsettled the realm of the life sciences by divorcing any moral design from the processes of biological evolution, Machiavelli proposed an ethics grounded solely in the shifting circumstances of human relations, not in divinely revealed universal moral values.

Historiography:

The Prince has been described as a satire (Spinoza and Rousseau), a mirror for magistrates,  and a handbook for gangsters (Russell). Machiavelli has been described as an anguished humanist (Croce), a passionate patriot, a cold technician (Cassirer), an critic of statescraft speaking solely to his time (Herder), a prophet of the modern, centralized state (Hegel), the supreme realist (Bacon), an aesthete seeking escape into a glorified Roman past (Koenig), an anti-metaphysical empiricist (Sabine), an artist of statecraft (Gramsci, Burkhardt), and most frequently as that 'murderous Machiavel' (Elizabethan scholars and poets), a man inspired by the Devil to lead good men to their doom.

Machiavelli's Morality: Rebutting Croce:

According to Croce, Machiavelli does not deny Christian morality; he only held that any policy based on such a code would end in disaster. The clash between Christian morality and political necessity, the incompatibility between morality and politics provoked anguish in Machiavelli. (Berlin defines 'morality' as the region of ultimate values sought after for their own sake, values whose recognition alone enables us to speak of "crimes", to morally justify or condemn any action.)

Berlin objects to this effort to confine ethics to a  realm where the source and criterion of value are the word of God (or eternal reason, that inner sense of knowledge of good and evil which speaks directly to the individual consciousness with absolute authority.)

Berlin argues that Machiavelli cites the time honored ethics of the Greek polis which, as described by Aristotle, men by their nature must live in communities and forge ultimate values therein. Political conduct is intrinsic to being human and its demands are intrinsic to living a successful life. The ethics of Machiavelli are derived from understanding the purpose and character of the polis- and although this conception of good and evil may not be absolute in some ideal, universal sense, it is connected to the ultimate good of the community. So the art of colonization (or of mass murder) may condone some actions as useful, they are not in the ultimate interest of the community and so can be judged to be wrong.

Machiavelli is not contrasting two autonomous spheres of behavior: the political and the moral. He is contrasting his own political ethics with another ethical conception which governs the thinking of many. So he does not reject Christina morality in favor of amoral game playing; his system affirms the classical sense of morality. He loved his country more than he loved his soul.