So Scythe did some coverage of creatures from Magic: The Gathering on his blog a while ago. They were all from older sets, but that doesn't mean that more modern blocks (groups of sets) haven't had some interesting creatures of their own.
Let's start with the Eldrazi, from the appropriately named Rise of the Eldrazi set.
The Eldrazi are eldritch abominations from the Blind Eternities, the spaces between planes. They eat mana, and will descend on planes to do so, leading to the plane's destruction. Three planeswalkers (powerful magic users who can travel between planes-it's a bit complicated) decided to try and stop them. This ended when the three Eldrazi titans above were imprisoned on the plane of Zendikar. For thousands of years they were imprisoned until, by apparent accident, they were released, spawning broods of ickle little abominations to destroy Zendikar.
So far I haven't heard whether the set's story ended with the Eldrazi being defeated or not.
We move from one set of villains to another, Magic's big bads, the Phyrexians. They kind of fell out of favour in the past several years, but they've made a big comeback in the Scars of Mirrodin set. The Phyrexians are more of a virus than a race, spreading via a black oil that transforms organisms into disturbing blends of flesh and metal.
Currently they're trying to take over the metallic plane of Mirrodin. As its inhabitants are already partially metallic, the Phyrexians seem to have half their work done for them. Art from the upcoming Mirrodin Besieged set, showing quite a few of the protagonists from the previous Mirrodin sets as Phyrexians, seems to confirm that the Mirrans are completely fucked.
But my favourite set/block in terms of creatures is the Lorwyn/Shadowmoor block (well, they're both individual blocks, but they're the same block flavour-wise). They were based on the mythologies of the British Isles, and also, to an extent, fairy tales. Lorwyn was an idyllic plane, perpertually sunny (really, the sun never went down very far), and lacking in maelevolent things. Well, aside from the elves, who were so obsessed with beauty that they hunted down anything they considered an 'eyeblight'.
Then something called the great aurora happens, and Lorwyn becomes Shadowmoor, a plane of perpetual twilight based on the darker aspects of fairy tales. The change affects the inhabitants too. I'll show this with one character, as she appears in Lorwyn:
and as she is in Shadowmoor.
I love the Shadowmoor creatures because they're just so downright creepy without having to be multi-limbed monstrosities with multiple mouths. Well, aside from the scarecrows. They're pretty weird.
There's even a Nucklavee, though it looks nothing like the actual thing.
I got these images off magiccards.info, just so you know where to look. The official card database is crap, the images are tiny.