Some of the memory crystals in paintings are from absurdly difficult Elites. (some are from lv90++ dungeon rank Elites, like Cloud's and Cyan's)
In contrast, all memory crystals from events thus far have been at the halfway Elite mark, or less (~lv60 dungeon rank or less). Many are within arms reach if you can beat the final boss on Classic and get the event character.
To answer your question, there have been some balance changes, but at the start of the global service Rydia and Cloud were party staples (Rydia's only other alternatives at that point was Black Mage (lol) and Tyro (lol lol)). When Aeris event came about, she replaced White Mage (or Paladin Cecil) as primary healer, but with the plethora of white mage events this past month that's probably not a valid comparison anymore. Vanille, Garnet, Yuna all make excellent white mages if you've gotten any of them.
I think a good piece of medium term advice is, when the XP daily comes about, see if you can do the first stage of the Hard daily. If you can, that's the first gateway to being able to level your dudes to 50, and/or level alternatives. The idea is you don't need to do the entire 3 dungeons or go for mastery. If you can survive one wave by blowing all abilities, you should be able to Friend Summon AOE your way past the next two, and get a shit ton of XP. Then you quit/repeat. Savescumming (closing the app and restarting) if you get bad ATB rolls and the enemies kill any of your guys first also helps.
edit: last note; There's a very tangible difference for as little as 10 character levels. Not only do you have more HP (~300-600 more depending on the character), you get hit for less because your DEF/RES stat is more robust. (In fact 10 levels is the equivalent of what characters get when fighting in their home realm (Record Synergy bonus) and is something to watch out for even at current endgame lv50-65 characters when considering lineups) Meaning yes, there's a very tangible difference from your current ~lv38 and lv50.