Removing armor speed penalties

[Elysiume]

I recently realized that base speed doesn't have a fixed penalty from encumbrance. After 40', you start getting falloff, with a 50' base speed equating to a 35' reduced speed. I'm a cleric of Desna, and I've been popping Longstrider and cruising around at 40', which isn't correct. My group is all quite new, and it just hadn't come up. Which brings to me to...what methods are there to remove heavy armor speed penalties in Pathfinder? Methods I'm familiar with:

Mithral (http://paizo.com/pathfinderRPG/prd/coreRulebook/equipment.html#mithral): Mithral armor decreases the speed penalty class by one, giving medium armors no speed penalty, but not helping heavy armor all that much.
Be a dwarf (http://paizo.com/pathfinderRPG/prd/coreRulebook/races.html#dwarves): A dwarf's base speed is never modified by armor or encumbrance.
Be a fighter (http://paizo.com/pathfinderRPG/prd/coreRulebook/classes/fighter.html): At 3rd level a fighter ignores speed penalties from medium armor, at 7th level a fighter ignores speed penalties from heavy armor.
Sash of the War Champion (http://paizo.com/pathfinderRPG/prd/advancedPlayersGuide/magicItems/wondrousItems.html#sash-of-the-war-champion): Granting 4 levels of fighter for the purposes of armor training would let you use mithral heavy armor, but RAW isn't clear on whether non-fighters can leverage this. It doesn't say they can't, but this is probably up to GM fiat.
Effortless Amor (http://paizo.com/pathfinderRPG/prd/ultimateCombat/spells/effortlessArmor.html): A 2nd level spell for a clerics, inquisitors, magi, paladins, and rangers. Standard action V+S, 1 minute/level, ignore all armor encumbrance.
Wearing light armor: ...

I'm not a dwarf, and I don't really want to delay my spellcasting for levels in fighter (either for the class feature itself or to activate the sash, as my GM ruled you need fighter levels). Wearing light (or even medium) armor gets a bit hairy, as I'm part of an extremely squishy party, with only one (of five) other players that primarily melees.

This leaves as my options:

Wear light armor: We're basically down to 1/6 frontliners.
Wear medium mithral armor: I could probably still frontline, but it would be harder.
Effortless Armor: Effortless Armor fixes all of my issues and lets me throw on some adamantium full plate (eventually), but burns a standard action every combat--at 1 minute/level, this isn't a cast-it-in-the-morning spell.
Be slower: Taking 30' without Longstrider or 35' with.

I may be over-focused on movement speed here, but I'm trying to hold fast to Desna's travel aspect, while also trying to provide what my party sorely lacks. I also don't have enough Pathfinder experience to know how much my options would hamper me in the short and long term.

Will I really feel the pain of -3 AC from a breastplate vs. full plate?
Will I really feel the pain of using mithral vs. adamantium?
Will I really feel the pain of spamming Effortless Armor?
It'd be nice to use full plate and a lesser rod of quicken to cast Effortless Armor, but that's really pricey.

[Particle_Man]

Maybe work on improving your dexterity such that light armour or medium mithral armour is almost as good a deal protection wise as heavy armour would be? And in the meantime, work on increasing your movement rate such that even heavy armour doesn't hurt you that much?

[Tuvarkz]

What is the content allowed? Fusing, from DSP's psionics, is a +1 property that reduces the armor category to one lighter, stacking with mithral to make heavy armors work as light ones, reducing the ACP by 1 and increasing the max dex by 1 on top of that.
Steelbone Frame kinda works too, although it's just a couple rounds per day, which is hardly enough.

[Elysiume]

Maybe work on improving your dexterity such that light armour or medium mithral armour is almost as good a deal protection wise as heavy armour would be? And in the meantime, work on increasing your movement rate such that even heavy armour doesn't hurt you that much?My dex is 12, and I hesitate to improve it much further because all it'd be giving me is AC and reflex save. I'm not doing any ranged attacks, and won't be using finesse, so that'd be a significant investment for only moderate gain.

With the travel domain and Longstrider, my base speed is 50, which is past the falloff point for increased speed. I'm at 30' in general, 35' if I cast Longstrider. Casting Effortless Armor would get me to the full 50', with the additional benefit of chopping off part of the ACP, at the cost of burning a 2nd level spell slot (less important at later levels) and a standard action (important at all levels).

What is the content allowed? Fusing, from DSP's psionics, is a +1 property that reduces the armor category to one lighter, stacking with mithral to make heavy armors work as light ones, reducing the ACP by 1 and increasing the max dex by 1 on top of that.
Steelbone Frame kinda works too, although it's just a couple rounds per day, which is hardly enough.Generally CRB+APG are always fine, UC/UM/UE/ACG/ARG case-by-case. We're not really using any of the more exotic stuff, so I think third-party would probably be too far.

[Firechanter]

Similar troubles here, though my toon isn't a Cleric but a Paladin rocking Heavy Armour.
That Paladin spell comes online rather late and has a high opportunity cost: one 2nd level spell slot (of which a Paladin has very few) and one action to cast - meh.
I can see myself investing into Boots of Striding and Springing, but it's annoying that 3500 of the 5500GP purchase price are being sunk in a function that I'll never use anyway (the Springing bit). If I could get just Boots of Striding without Springing for the 2000GP it should cost according to the guidelines, that would be an instant buy.
Technically I might also get me the Travel Domain via Sacred Servant, but it's not really what I had planned.

Here's another pointer for you:
Oracles can get revelations that either increase their base speed or reduce movement penalties -- I don't know them by heart though, and the main thing that's putting me off off that approach is that I find each of the Curses too detrimental. Lame would defeat the purpose, not being able to communicate with your buddies (i.e. Tongues) sucks balls, and practically all the other ones are pure poison for a melee character.

[Elysiume]

Similar troubles here, though my toon isn't a Cleric but a Paladin rocking Heavy Armour.
That Paladin spell comes online rather late and has a high opportunity cost: one 2nd level spell slot (of which a Paladin has very few) and one action to cast - meh.
I can see myself investing into Boots of Striding and Springing, but it's annoying that 3500 of the 5500GP purchase price are being sunk in a function that I'll never use anyway (the Springing bit). If I could get just Boots of Striding without Springing for the 2000GP it should cost according to the guidelines, that would be an instant buy.
Technically I might also get me the Travel Domain via Sacred Servant, but it's not really what I had planned.

Here's another pointer for you:
Oracles can get revelations that either increase their base speed or reduce movement penalties -- I don't know them by heart though, and the main thing that's putting me off off that approach is that I find each of the Curses too detrimental. Lame would defeat the purpose, not being able to communicate with your buddies (i.e. Tongues) sucks balls, and practically all the other ones are pure poison for a melee character.I'm at the point where stacking more speed gets even less cost effective, since I'm only getting 2/3rds benefit from it. I'm also expecting to have Longstrider up most of the time in a few levels, which wouldn't stack with the boots (both are enhancement bonuses). The Travel domain could be nice for you; the untyped +10 base speed is solid, and it gets you access to teleportation down the line.

Haunted/Wasting aren't totally crippling, but they're all kind of rough. The Flame mystery has Cinder Dance (+10 base speed, gives bonus feats). The Flame mystery also has a revelation that lets you sprout fiery wings as a swift action (7th level or later) and fly with a speed of 60', which is pretty cool.

[Dekion]

You have listed most of the ways it can be removed, aside from some random archetypes and prestige classes that get abilities similar to a fighter. Is it absolutely necessary to have a 50 ft. move? Given that you could move 35 ft. per round in medium armor, you are already doing better than just about anyone in medium armor, and many in light/no armor. I know it's nice to have a lot of options for tactical positioning, but you may be feeling like your character is handicapped when they really are doing pretty good. Additionally, mithral armor is a good choice, it would resolve that issue for medium armor, and, personally, I would't be burning the feat for heavy armor proficiency as a cleric, there are a lot of other feats that are better. I didn't see you mention that you had or were planning to, but since clerics don't get heavy armor proficiency in Pathfinder, I'm assuming it was part of your plan.

[Elysiume]

You have listed most of the ways it can be removed, aside from some random archetypes and prestige classes that get abilities similar to a fighter. Is it absolutely necessary to have a 50 ft. move? Given that you could move 35 ft. per round in medium armor, you are already doing better than just about anyone in medium armor, and many in light/no armor. I know it's nice to have a lot of options for tactical positioning, but you may be feeling like your character is handicapped when they really are doing pretty good. Additionally, mithral armor is a good choice, it would resolve that issue for medium armor, and, personally, I would't be burning the feat for heavy armor proficiency as a cleric, there are a lot of other feats that are better. I didn't see you mention that you had or were planning to, but since clerics don't get heavy armor proficiency in Pathfinder, I'm assuming it was part of your plan.It was part of my plan, I was going to take it at level 3. The more I thought about it, the more I thought that my real issue was with the fluff of heavy armor encumbrance. I don't need to be zipping around at 50' per move, I just hated the feel of moving more slowly. As Cleric of Desna, the goddess of liberation and travel, it doesn't feel like I should be encumbered by full plate (even if I'd be faster than more unencumbered people).

If I'm not going to feel overly punished with a mithral breastplate, I'll probably make that my plan. I'm the only shield-user in the party, so I'll actually be close to parity with the heavy-armor-wearing Fighter, potentially passing him once I can start enchanting my shield. Of course, an issue is that I won't want to wear any armor other than mithral, which limits my choices. I think the roleplaying benefits outweigh the rollplaying costs for me here.

It also means I need to pick a different feat to take at level 3, but I could probably take Extend Spell, or grab SF:Conjuration to prepare for Augment Summoning.