Fenring is indeed the Emperor's closest friend, and it is mentioned that it was out of friendship that Fenring refuses the order:
The second major
evidence of the Count's friendship was negative. He refused to kill a man even
though it was within his capabilities and my father commanded it. I will relate
this presently.
-"Count Fenring: A Profile" by the Princess Irulan
There is one rather overt reason why Fenring refuses the order. As DVK mentioned, Fenring was a failed attempt at the Kwisatz Haderach project. He had much of the potential, and some of the talents, that the Bene Gesserit bred for, but a genetic anomaly caused him to be a eunuch, making him a dead end for his branch of the breeding program. His abilities protected him from Paul's, and made it entirely possible for Fenring to actually follow through and kill Paul. Paul realizes this just before the Emperor gives the order:
The Emperor's errand boy, Paul thought. And the thought was a shock crashing
across his consciousness because he had seen the Emperor in uncounted
associations spread through the possible futures--but never once had Count
Fenring appeared within those prescient visions. It occurred to Paul then that he had seen his own dead body along countless
reaches of the time web, but never once had he seen his moment of death.
Have I been denied a glimpse of this man because he is the one who kills me?
Paul wondered.
Paul also realizes the source of Fenring's powers, and feels a sudden and overwhelming kinship with Fenring. This emotional connection is a large part of why Fenring refuses to kill him:
Slowly, Fenring moved his head, a prolonged turning until he faced Paul.
"Do it!" the Emperor hissed.
The Count focused on Paul, seeing with eyes his Lady Margot had trained in
the Bene Gesserit way, aware of the mystery and hidden grandeur about this
Atreides youth.
I could kill him, Fenring thought -- and he knew this for a truth.
Something in his own secretive depths stayed the Count then, and he glimpsed
briefly, inadequately, the advantage he held over Paul -- a way of hiding from
the youth, a furtiveness of person and motives that no eye could penetrate.
Paul, aware of some of this from the way the time nexus boiled, understood
at last why he had never seen Fenring along the webs of prescience. Fenring was
one of the might-have-beens, an almost Kwisatz Haderach, crippled by a flaw in
the genetic pattern -- a eunuch, his talent concentrated into furtiveness and
inner seclusion. A deep compassion for the Count flowed through Paul, the first
sense of brotherhood he'd ever experienced. Fenring, reading Paul's emotion, said, "Majesty, I must refuse."
However, that unexpected kinship between Paul and Hasimir is not the only reason why Hasimir refuses the Emperor's order. As was implied by Irulan, Hasimir seems to feel that disobeying the order is his duty to the Emperor, as his friend:
"We have been friends, Majesty.
What I do now is out of friendship. I shall forget that you struck me."
While this could be interpreted as "I will forget that you struck me out of friendship," I believe he is saying that his refusal is out of friendship. Irulan certainly seems to agree. My speculation as to why this is the case is that Fenring sees the honesty and "hidden grandeur" in Paul, and realizes that Paul will spare the Emperor's life, and not allow him to be mistreated, but that if Paul were to be killed, the Fremen would slaughter the Emperor, and every single member of his family and entourage.
As an additional influence, Hasimir loves his wife, who is a Bene Gesserit, very deeply. The previous scenes with the two, when Lady Fenring goes to Giedi Prime to seduce Feyd-Rautha, demonstrated that Fenring respects and understands (to an undefined extent) the goals of the Bene Gesserit, and likely feels that it would be a mistake to destroy the culmination of the breeding project he himself was once part of, knowing how highly the Bene Gesserit valued the program.