1) Give top Gear (i50+) 1-2 materia slots. Give vanity and dropped weapons (Zantetsuken, HM Primal) weapons varied between 3~4 slots. (or just on average more than normal drops)
2) Have i70+ dungeons drop specific rare materia that provide special skill boosts and add effects to the weapon. (+100 skill speed, Vampire damage, job skill boosts, ect) These materia are treated as loot in a dungeon, you roll and need on them based on class.
3) Do not allow the special materia to provide raw damage boosts. +20 Strength is a no-no -- that is linear progression.
3) Make melding these high-end materia 100% with no failure rates, with the ability to remove them intact. (Or rather, allow them to fail based on crafter stats, but do not allow them to break. This could help create a DoH market, except without discouraging using the system.)
4) Put some of the materia in the shop for the price of tomes to keep with the current progression model
-KABOOOOM endgame progression is no longer linear, dungeon runs now have purpose, there are multiple ways to gear the same character, there's a alot more to aspire to endgame, Materia is no longer useless, lv50 crafting jobs are no longer (completely) useless.
-Higher ilvl weapons still provide overall greater DPS boost, but the extra slots on non-optimal gear allow players with access to higher materia the ability to potentially make them useful in niche situations due to having more slots.
Essentially, this encourages the same progression the game has now (dungeon drops and myth tomes) except with an added layer that keeps old content relevant by allowing it to feed off content released later.
Best of all, the only thing it really requires are systems that already exist in the game now.