Interesting. I wouldn't mind looking into giving the player more choices from the get go. Effective, and creative party setups could be a really interesting dynamic, which I felt was very lacking for the majority of FF7.
Anyway, I have been playing Digital Devil Saga 2 lately. I'm going through on the hard difficulty, and it is some of the most fun I have had with an RPG. The basics are that most everything has a weakness, or small list of actions. Furthermore, your party is very limited in the amount of skills they can have active during battle. Ultimately, it is very simlar to FF7's materia setup. You have a max of 8 skill skills per character. Skills are individuals skills/spells, but the end result is something along the same lines.
Attempting to mimic the same format wouldn't work, because the Shin Megami Tensei Press Turn system is VERY reliant on exploiting weaknesses, not to mention protecting your own. However, I feel that giving the player Elemental (blue support) materia as early as possible, and a few other support, independant (purple), or command materias early on would GREATLY improve some of the strategy. Early on it may be as simple as finding out a boss' weakness, and using Elemental->Fire on everyone's weapon., or determining that most (if not all attacks) are ice, and using Elemental Ice on armor is the way to go. Basically, strategy would be pregame oriented. Yes, it is a little disapointing, since I like involved encounters, BUT we kind of need to work with what we have. Giving the player all the tools they need to make good pre-game strats is FF's strong point. Giving them the motivation, and enemy configs to exploit them... not so much.
Ah well, if I didn't say as much earlier, don't sweat this little deviation in discussion, Skillster. I think you are more of less on the same track, BUT using the existing FF7 gameplay feel (gradual progression/accumulation of statistics and equipment/items) which is good. I don't think you wanted to completely overhaul the FF7 gameplay, but make it a bit more interesting and challenging. What nl and I are mentioning is more along the lines of a big overhaul to the game progression/feel.
I may look into this, and experiment further. It'll be a while, though. I don't have the best of PC configurations right now.