This has been done (to an extent) in the NT mod; after visiting the bottom of the North Crater, an option unlocks (triggered through an NPC in the Highwind's Operation Room) to swap party leader to either Tifa or Cid. I had to add a lot of field code so that the game could handle them being party leader, and some were quite tough like the Gold Saucer, Great Glacier, and Wall Market due to all the script shuffling that needed doing.
It'd be nice to do it a) with all the characters, and b) from earlier in the game but the work involved would likely require that each scene be re-constructed from the ground up so that scripts don't clash when someone is party leader as opposed to just being a party member. Also, the World Map is a major sticking point like NFITC1 said; but there's also another potential problem with the way it has a priority system for who is displayed on the world map; if a higher priority character is swapped out/in vis PHS and the game is then saved, closed, and loaded (without closing the menu), the player will find themselves marooned at coordinates 0,0.
And finally, animations are a blocking point. The Gold Saucer was a bit scrappy for me because there's a lot of unique animations there and Tifa's skeleton is different (Cid can use Cloud's animations to an extent, but his feet snap up at a 90' angle). Beyond that, characters like Red XIII, Vincent, Yuffie, and Cait Sith would likely struggle with basics like climbing ladders, going through crawl-spaces, and other basics.