Is he? Until Pompey really championed Alexander in the eyes of Romans (mainly to play up his own accomplishments) Alexander was pretty generally viewed as a bastard by Greeks and Romans alike, although the Macedonians and Alexander's successors were not surprisingly fans of his. Several of the histories of Alexander that were read in antiquity, all lost, such as Callisthenes' and Ptolemy's, were written by his supporters (although Callisthenes, ass-kisser though he was, eventually grew disillusioned with Alexander and Ptolemy seems to have told a more or less strictly factual account) and may have cast him in a better light, although we can't know because they're lost. Even then, Alexander didn't really become anything resembling an exemplary person until writers of the Second Sophistic attempted to recast him as one of the great Greek heroes that they were writing about so much at the time. But the Second Sophistic writers quite consciously were building a sort of mythology around the Greeks of the Classical Period, and Alexander's image fit well enough. Even then, what they have to say is by no means all flattering. All the sources of Alexander's life that survive are either from late antiquity or from the Second Sophistic, and together they paint a picture of a very complicated person, one who contained quite a lot of nasty traits. Even Alexander's champions recognized that he was prone to excess, fits of madness, a total lack of temperance and moderation (which was a big deal for the Greeks as well as the Romans), bloody rages, etc. I mean, the guy ran one of his best friends, a man who had saved his life in battle, through in a drunken rage.
I don't know much about Alexander's perception in the Middle Ages, but as I understand it he was seen mainly as some sort of adventuring hero. In Western Europe the Greek sources in which Alexander's life is recorded were unreadable, but Alexander's life and exploits were preserved in the Alexander Romance, a series of tales about Alexander that were originally in Greek and may (but probably do not, at least in any significant quantity) trace some of their origins to Alexander's court poet Callisthenes. These were already becoming popular in late antiquity, and during the Middle Ages the Latin versions of the poems were widely read--indeed, the text was translated into the vernaculars of pretty much all of Europe, and Arabic, Georgian, Armenian, and Syriac versions were read in the Middle East. Almost all the stuff that's in those stories is nonsense or is totally unattested, such as the glass bubble that Alexander supposedly took to the bottom of the sea, but it was extremely popular and adventurous nonsense, which undoubtedly served to increase Alexander's popularity during the period. Again, I don't know a whole lot about Alexander's reception during the Middle Ages, so that's as far as I feel comfortable commenting.
Modern scholars are constantly bickering about Alexander's character. The German scholars of the Victorian Period were big fans of Alexander's, and in the early 20th Century the influential scholar Tarn (who wrote the first, and probably still the most exhaustive, modern life of Alexander) idolized Alexander, hypothesizing that Alexander's actions were motivated by an intellectual desire to improve the condition of the human race. Tarn proposed that Alexander was attempting to craft what he called the "Unity of Mankind," although even in his magnum opus he was never able to really back it up with evidence. It is to Tarn that we owe the unbelievably antiquated perception that still pervades popular culture of Alexander as the man who brought great Greek civilization to the backwards barbarians and the decadent Persians. The man was, and still is, tremendously influential--his biography of Alexander and the numerous journal and reference articles he wrote on Alexander stuck in everyone's memory. But even in the 30s when it came out it was highly contested, although his work was widely read and after a while largely accepted. M. Cary wrote a very good review of Tarns's article "Alexander the Great and the Unity of Mankind," the 1933 work in which Tarn's vision of Alexander really began to take form--as Cary says, Tarn presents Alexander in an "unfamiliar light," although he was willing to buy it at the time. Tarn's work has been thoroughly swept aside--Badian (who hated Alexander) launched an all-out frontal assault on Tarn in the 50s, and meticulously shot him down. But even so, Tarn's legacy is very much alive, and you still see Alexander turn up as a great adventurer, conqueror, and hero in a lot of high school and even college textbooks, which tend not to delve into the horrible things which he did on the side. The scholarly jury on Alexander is still out, though. For a time Badian's picture of Alexander (my father, who studied under Badian, likes to mention that Badian once told him that Alexander was "a callow youth," which is almost praise compared to some of the opinions Badian had on the guy) was pretty dominant, and I would say that although a lot of what Badian said has been superseded most scholars would agree that Alexander was ambiguous at best, a point that Badian's pupil Green tried to make in his biography of Alexander.
EDIT: I spelled Cary's name wrong >.<
SECOND EDIT: Also, I accidentally deleted this exact same post and had to put it back up. Methinks my computer has finally begun to forget the basic functions of life...
TRIPLE EDIT: I wrote Seleucus instead of Ptolemy, it's fixed now. Today's not my day, I guess I'm still in Japanese mode from my final this morning :/
I have a followup question: does the fact that he "only" conquered from a already established superpower make his conquest more condonable in peoples eyes? As far as I know he was at war technically only with Persia and a bit of India at the end?
I believe the simple answer is that Alexander went East and was only lauded by people in the West (several decades/centuries after his death).
Less documents make it to the West over time, which means less competing narratives. Therefore, when someone like Pompey wants to champion Alexander there are very few people who would have direct ancestors that were affected by Alexander, and the written copies that would have voiced dissent weren't widely available.
Macedonians were perceived as barbarians by the Greeks and they were very bitter about being conquered by Alexander's father so they didn't think highly of Alexander either. Like many of our perceptions we do as the Romans do. Alexander's exploits fits nicely with the narrative of Romans creating an empire and delivering civilization to other peoples. Alexander was a military leader first and a civil leader second. In the later Roman Republic period this is exactly what the most powerful Romans were so they idolized Alexander.
I would venture to say that it was his background in education that would have lead to a lot of people feeling that way. Maybe, to some, it's more acceptable for a conqueror to wage war and acquire a lot of territory if he is an educated man, and spread ideas that were popular among large groups of people (particularly those writing books on his accounts, biographies [past or present], etc.).
Creating a hybrid culture of Greek and Persian (Hellenistic) also built a bridge that allowed for a lot more people to come together from both sides to bring that cultural gap together.
Founding cities is also something that I could see causing people to think fondly of Alexander, as it is thought that many advancements in mathematics, science, medicine, and even philosophy came out of cities that he founded (or regions that he "liberated").
Partly because of the passage of time. We tend to give more moral leeway to ancient conquerors than modern ones. Secondly because from a Western perspective he is associated with the spread of Greek civilisation, which we see as a good thing.
There are ways in which Alexander was different than previous conquerors, so it might be more accurate to say he was "less bad" than the previous examples he had to consider at the time. We have the perspective of subsequent history to rate leaders by, but in contemporary eyes, he was somewhat "progressive"?
One intensely personal way was that the conquered territories were allowed to retain their religion, instead of attempting to convert them to the emperors religion. The local priests were not slaughtered.
From a purely militarily perspective, I think it would be a safe bet to say that Alexander "The Great" faced the massive hordes of the Persian empire with thoroughly superior arms and armor and discipline, but if one takes into account the state of such an army like that of Persia at the time, it becomes clear that it is not even close to an equal fight; hordes of men from all reaches of the empire, most likely armed with short, light spears, poor scale armor if they had any at all, and most likely wicker shields. Weak willed opponents with weak willed commanders versus the Macedonian Phalanx. That is why I do not consider him among the greatest military minds in history, it was pretty much a slaughter and land grab for the taking. As far as Hellenistic culture is regarded by modern history, I am unlearned. One great thing to come out of Alexander's conquests though was the Ptolemaic civilization. The lighthouse and library of Alexandria. The undisturbed flourishing of Hermetic and Gnostic schools of thought. Alchemy, astronomy, and other fields were patronized in Ptolemaic Egypt.