I think the Greeks did most of our work for us already.



- A plane of origin for fiends
Welcome to Tartarus, Hades, Hell, the Underworld. There's a cave entrance somewhere near Athens. Fiends come up to collect the souls of the dead or make hell for the living. Deeper down is the blackest pit, the Chaos, where pure entropy resides and demons are born.

- A plane of origin for celestials
Olympus, Heaven, Home of the Gods, even further up than the Sun and Moon and within a sky held up literally by mountains (and one poor doomed titan).

- A plane of origin for elementals
When Law and Chaos combine, I am Captain Elements! The world is full of places where the divine sparks mingle and create raw elemental states. Calderas of fire and lava are where fire elementals were born from. The sky itself and infinite oceans and deepest caverns make up the rest. There's no one location for these things, they're as mingled as the Ethereal Plane and connected through bendy laws of physics and warped space-time.

- A place for deities (which can include the first three)
They live wherever they damn well please. Olympus might be where most reside but the god of death prefers living with his wife in Hell and the god of the oceans prefers his island of Atlantis. The blacksmith god never leaves his volcano forge and the war god is at home on the battlefield.

- An afterlife (which can include the first three)
The bad souls go to Tartarus while the good souls go to Elysium. Tartarus as we know is in the underworld but Elysium, according to Homer, is a group of islands on the western edge of the world. Paradise Island sounds like a great place to spend eternity.

- A way to travel between planes
Walk. Or take a pegasus. Or a flying chariot. Or a boat. Actually, most of the traveling happened with boats... even souls are ferried across the River Styx with a boat. And Odysseus and Perseus had all kinds of crazy adventures in weird places. Boats are just magic. This is officially the Spelljammer campaign setting.

- A way for spells and monsters that use the Astral and Ethereal planes to work
Ethereal Plane is the hidden side of the world that can only be seen by the dead and gifted. Souls wander until they're collected and returned to their proper afterlife locations. The Astral is simply Oceanus, the titan that encompasses all rivers, lakes, and seas again connected through Möbius logic. You can get anywhere by sailing the River of Ocean, which yet again makes boats the best way to plane travel.