While we're on the topic of strangely intelligent creatures, how about another weird New Zealand parrot, the kea? It's a carnivorous mountain parrot. I've seen them working in teams to demolish a motorbike's cargo while the owner was away. Smart, like all parrots, and quite destructive, but cute in their own way.
The giant squid is another cool one, and not just because they're sometimes called kraken. (We've got a few of those in deep New Zealand waters too. Pity they explode if they approach the surface, or tourism would be far more interesting.) Some people speculate that they can grow to sizes far beyond that of any recorded specimen, because they've found sucker marks on sperm whales (that's the cachalot if you swing that way) that are many times bigger than any sucker found on a kraken yet... and those puppies are big.
Lungfish are always good. "Ack! There are fish falling from the trees!"
There are birds in the Amazon that have teeth, but I've forgotten their name.
Speaking of the Amazon, ever hear of the Basilisk Lizard? It doesn't petrify its victims, but it can run on water, thanks to its long toes, low body weight and immense speed.
Or the extinct Madagascan Pygmy Elephant? (I think it was Madagascar. I'm not sure.) Just to prove that today's elephant is not in fact a shrunken, stunted version of the woolly mammoth, but is a more average historical pachyderm.
Giant, flightless vultures like (larger, stumpy, carnivorous) ostriches? (Also extinct, and a good thing for us I might add.)
For the fellow who mentioned horseshoe crabs... aren't they related to trilobites? Those things that went exting, like, one or two hundred million years ago? I've got a fossil trilobite on my shelf. And an ammonite (the ones like squid in spiral shells).
For the really cool and freaky stuff, I'd investigate cryptozoology. By its very nature it's unproven, but things like the Gobi Desert Spitting Death Worm do sound cool, don't they? And a hundred years ago (give or take), the mountain gorilla and giant panda were unknown to Western science, thus cryptozoological specimens themselves. Just to put that in perspective.
No links, sorry. But I'm sure a few creative searches will turn up something...