Hades - Fire/Dark - Think the Balrog from the Lord of The Rings, The Three headed Dog Cerberus, or like a 'grim reaper' archetype.
Zeus - Electric/Flying - Zeus often took the form of an eagle or bull, and was the Sky God who wielded the famous Lightning bolt. Tauros/Braviary + Zapdos?
Poseidon - Water - Any kind of large fish or sea creature, really - Dolphins, especially. Could kind of conflict with Kyogre, though.
Exellent suggestions! Especialy the zeus thing. A fusion with those would certainly be unique. I personaly was thinking a lightning pegasus with horns etcs, but maybe a bird is the way to go.
Poseidon should also be distinctiveas a water legendary but yet unique. A dolphin certainly would be a new idea.
The hades as a grim reaper archetype is a little mixed bag for me. Yes the grim reaper represents death and is an easy to follow consept. But Im feeling a little worried about these humanoid type pokemons. I dont know. Maybe I just cant Imagine them well. :'D