It's weird that Overland Flight and Plane Shift are both 5th level spells. Crossing the Crystalmists doesn't seem that impressive when you can travel to other planes of existence. In terms of opening up adventure locations, the most important spells are:
Water Breathing, available at 5th level
Overland Flight at 9th
Plane Shift at 9th (13th for wizards)
The best solution would probably be to bump Plane Shift to being a 7th level spell for clerics, as it is for wizards. Other planes are really the final adventure location for a D&D campaign, nothing is more removed or more alien, so it seems wrong to get it at only 9th level, less than halfway through the 1-20 progression.