What's the deal with Avada Kedavra? It kills its target, fine, but so do many other things. Why is Avada Kedavra specifically banned, rather than banning "killing people"? Why is killing someone using that specific magic considered worse or different than killing him with any other means?
I think part of the premise of your question is incorrect. Murder is considered a crime in the wizarding world, just as it is among the Muggles. If a wizard kills another wizard with a gun or a knife, I'm sure it would be punished accordingly.
In the books, we are told that Avada Kedavra is one of the three Unforgivable Curses, along with Cruciatus (pain) and Imperius (mind control). (As I recall they first appear in Goblet of Fire.) These three have no legitimate purpose and, as we see in the later books, they make it very easy to do horrible things to people. Therefore they are banned.
The point about Avada Kedavra is that it's a weapon. Wizards are not allowed to use it for the same reason that people in Britain are not allowed to carry handguns. If a British person used an illegal handgun to commit murder, this would be treated as an aggravating circumstance and result in a harsher sentence. We can assume the same would hold true in the wizarding world.
Also, it's important to remember that wizards carry their wands at all times. So they could use Avada Kedavra any time they want; it's a similar situation to the Old West of cowboy movies, where everyone is carrying a loaded gun. The only reason the wizarding world does not degenerate into an OK-Corral level of violence is a very strong social taboo against using magic to kill people.
Edit: [This edit may be incorrect, see discussion of Moogle's answer.] As pointed out by Moogle, Avada Kedavra requires a strong degree of anger and desire to kill the other person. So it's as if someone in our world killed another person in a particularly violent and sadistic fashion. That would also be considered an aggravating circumstance.
Well firstly, there is no defence against the Killing Curse except for Sacrificial Protection (which still results in a person's death). So while murder is still murder, at least with other spells/means a wizard/witch has the possibility of defending themselves.
Secondly, using the curse requires great willpower, and a strong desire to kill the other. So while somebody could shoot somebody with a gun in a fit of rage, this wouldn't be possible with Avada Kedavra. This obviously tells us something about their mentality and what sort of person they are, and also suggests that they would feel no remorse. This is evidenced in Order of the Pheonix where Harry Potter was unable to effectively cast the Cruciatus curse on Bellatrix LeStrange, despite being enraged over the death of Sirius.
~Bellatrix LeStrange taunting Harry Potter about Unforgivable Curses during the Battle of the Department of Mysteries
For this reason, it is one of the Unforgiveable Curses (along with Crucio and Imperius), which carry a life sentence in Azkaban.
Avada Kedavra is the plot element which both distinguishes the main character and serves as the signature attack for his antagonist. An attack that is (by definition) as terrible as Voldemort himself.
Harry does not show any particular gift or skill at wizardry, nor a particular amount of intelligence or even some kind of shrewdness. The most basic and obvious petty tricks (household magic, everyday magic devices) which every young wizard uses without wasting a thought still surprise him even after 3 years at wizardry school. He also isn't particularly good looking or athletic, his only notable ability is flying a broomstick, which isn't a lot.
However, Harry is the single person in history who was bestowed the terrible death curse and lived. And not only that, the curse also bounced back to the Dark Lord and disabled him for over a decade, whereas before Voldemort had been more or less unchallenged and unstoppable(*).
This is what distinguishes an entirely unimpressive boy with no special abilities from a total loser and makes him the protagonist that stands out of the crowd.
All of this wouldn't work if the killing curse was only just another way of killing a person. It must by definition be the most terrible curse, in order to stand out.
The killing curse is not "particularly terrible" otherwise, except for the fact that you die. It is described in the books as a green light, and then you are dead. There is no mention of pain or a particular cruelty whatsoever. The depiction of what happens to the victims (such as e.g. Cedric Diggory in book 4) is very much suited for an "all audiences" rating. The lifeless body simply drops dead. Neither does the victim cry in agony or end up curled up in convulsions. In the later books, people who have actually experienced the death curse testify that there is not much to be afraid of, it is not painful and it is over pretty quick. From the reappearance of several characters as "ghosts" or "souls", one can conclude that the curse is not particularly devious insofar as it e.g. destroys (or robs) the victim's soul either.
Arguably, the killing curse might appear "more terrible" than other spells from an ethical point of view. Other spells may certainly cause a much worse death experience, such as for example a fire spell. Burning alive is without doubt a lot worse than seeing a green light and dropping dead. However, a fire spell, like most magic, may have other legitimate uses whereas the killing curse serves only a single purpose, snuffing out life. There is, however, no mention of any such thing in the books. This would be purely a reader's conclusion.
The death curse's main purpose remains being a plot device for drama and for giving the main character a justification in the story.
If the death curse was a real element of the story's universe, one would have to wonder why Voldemort and his Death Eaters are not killing everyone who gets in their way (including for example Dumbledore) on the first occasion. After all, there is no defense against it. Why would you use a spell that can be countered, if you have a spell that just kills anyone? How could a Death Eater ever (reasonably) get captured by an auror? Why would you fear Dumbledore if you can just snuff him out in an instant?
(*) This is however inconsistent with the later books which were in my opinion written by ghostwriters that didn't know (or care) much about the original stories.
As we learnt later in the series, using Avada Kedavra to kill tears the soul of the user of the curse. There is no reference to other forms of killing doing so. OK, so only a few seem to know this fact in the books, but it can be assumed that those who lay down the laws would know this.
Just my take on this fictional work; take it or leave it :)
The curse serves no other purpose than to kill. There can be no other intent other than murder.
Even if you were to miss, there's nothing to prove in court. There can never be a conviction of manslaughter in a case of death by Avada Kedavra, and any unsuccessful use of the curse is an unquestionable conviction of attempted murder.
The only possible question in the use of the Killing Curse is whether or not the user was under the Imperius Curse.
There doesn't seem to be a lot of concrete evidence in the books for any answer to this question, so I'll take a bit of a different approach in speculation: I'm not sure it's necessarily considered "worse," as opposed to just "in scope."
The wizarding world is very concerned with secrecy, and part of that secrecy lies in not attracting attention. We never hear of laws in the wizarding world that are related to matters other than magic and its misuse. Even though users of the Killing Curse are commonly called murderers (and rightly so), the actual crime for which they're tried and sentenced is use of an Unforgivable Curse. I believe that this is part of the ruse: Wizarding law only covers matters related strictly to magic, so that it does not interfere with Muggle law (which would attract attention from Muggle governments). Those who commit the things we typically think of as crimes, but do so without using magic, are likely just stripped of their wands and turned in to Muggle authorities for trial. Even those who commit crimes with magic, but do so in ways that could be handwaved by more mundane explanations, could be dropped off with a plausible story. Wizards have not shown themselves to be above lying to maintain secrecy.
But you can't do this with the Unforgivable Curses. No Muggle coroner would be able to find any cause of death for victims of the Killing Curse, nor would any Muggle doctor be able to recognize the tortures inflicted by Cruciatus, and even the wizarding world has trouble handling all the implications of the Imperius Curse. In other words, the Unforgivable Curses don't just commit horrible crimes, they do so in ways that cannot be explained except by magic. That makes them inherent breaches of secrecy, and handing the perpetrator over to Muggles would only make the breach worse.
This, I believe, is why the Unforgivable Curses are different: Muggles can't handle them. The wizarding world has no choice but to handle crimes like these internally, and this is why Azkaban was built.