I say we need a unicorn. A real one--Rapidash doesn't cut it. Maybe it could only be approached by females, and have a brother legend that can only be approached by males. Of course you could trade, but hey.
Maybe the male one could be a gryphon.
There could be an Androsphinx and a Gynosphinx as well, speaking of gender lines. They could be the new Latis. Ground/Flying, maybe? Rock/Psychic?
I'd also like to see a raven legendary, to go with the legendary position ravens hold in so many Native American tribal stories. Dark/Psychic?
A scarab beetle could satisify people's calling for a Bug-type Legendary.