I know that Steven Stone is in the game, but you never actually get to battle him which I find very disappointing. I feel like a suiting place to battle him would be at Mt. Moon; similar to his hiding place at Meteor Falls in Emerald where he's searching for rare stones. Mt. Moon is where, in the original games, the player chooses between the helix or dome fossil with the Super Nerd, and in the anime is depicted as an archaeological mega site. I know that this is your first hack, and it is a small hack more focused at making minor relevant changes. I believe that since he is present in the game, he should have been an opponent we could have faced.
Steven though is just like Red in that he is now wandering about rather than defending his champion title (although in HGSS he introduces himself as the Hoenn Champion), and I feel that Wallace who takes his place as the Hoenn Champion in Emerald would be a good opponent as well. I could actually picture him being the guy that Misty is caught with on a date at Route 25 prior to challenging her at the Cerulean City Gym. I'm not quite sure how hard it would be to change the script that this takes place in already, or if it would just be easier to write another one that does just about the same thing with Wallace taking the date's spot. I could picture him being re-encountered after having his date ruined at the Vermilion City docks waiting for a ferry, or better yet, cooing a Swimmer Girl or something. I could write a conversational script for these instances if this were something you'd be willing to try.
Just like Steven, Cynthia is also already present in the game and has a cameo in the Sinjoh Ruins sidequest. Once again however you cannot battle her which is really frustrating. Generation IV was the last series of games that I really 'got into', and I thoroughly enjoyed the battle with Cynthia at the end of Platinum, and her reappearance in Undella Town in Black + White. Similar to meeting her in Undella Town, I could picture finding her at one of the many potential vacation spots throughout the game. It's unfortunate that Kanto Route 19 didn't maintain the Summer Beach House from Pokemon Yellow, because that would work. More realistically, and tying in with her Sinjoh Ruins sidequest, it would make a lot of sense finding her in Ecruteak City seeking the knowledge of the Wise Trio on ancient Pokemon history.
Considering the Kanto, Johto, Hoenn, and Sinnoh regions all fall within the same landmass, and are within the generation IV canon, it would make sense to stop here with champions. The Unova, Kalos, Alola, etc. regions are based on places outside of Japan, and on a map are explained by Game Freak to be far off in the world rather than bordering regions like the original 4(not to mention they are from Gen 5, 6, and 7 respectively).
I would include one more 'Champion' however, Drake of the Orange League. I know that among the rom hacking community the Orange Islands are a sought after inclusion in just about any hack based in the Kanto region, and I feel like Drake would do great as a feature at the Battle Frontier. Rather than add the Orange Islands into the game(which would be sick if it was viable), have Drake appear at the Battle Frontier; which seems to actually be more akin to the unorthodox Orange League than it does to the main land leagues.
I know that Drake is an anime-exclusive character just like the islands themselves, but I would make a significant change to his title and the name of his League. In English we refer to his team as the Orange Crew, but in Japanese the name translates to Southern Cross. The Southern Cross, also known as Crux, is a famous constellation whose 5 most coveted stars are Alpha, Beta, Gamma, Delta, and Epsilon. Alpha, or Alpha Crucis, is the brightest star of the whole constellation, and based on the ranking of these elite 5 trainers it would seem Drake is the Alpha Crucis. In English his title is Orange Crew Supreme Gym Leader, while in Japanese it simplifies to Head Leader. I'd personally suggest appending his trainer class and name to: Southern Cross Alpha Drake.
I also thought about having Lorelei and Agatha make appearances as it seems they've retired from the Elite Four or been replaced for whatever reason. Agatha could be found in the basement of Brass Tower in Ecruteak City, or outside the House of Memories in Lavender Town expressing animosity towards the Pokemon Tower being turned into a Radio Tower. Lorelei could be found training at the Seafoam Islands or the Ice Path. There are also the Hoenn and Sinnoh Elite Four members that are all formidable trainers. Even though I feel the urge, I feel that adding the Hoenn and Sinnoh Gym Leaders would just get too messy because they wouldn't even be in their gym, and then there's the whole badges thing too...
As for the other 2 goals, the wonder cards are almost all exclusively pokemon. Of the wonder card pokemon, I believe all but 2 or 3 are 'unattainable' and the majority are also legendary. It would kill 2 birds with 1 stone if the wonder cards were in some way activated or attained, and it would allow the player to complete the extra sidequests pre-built into the game. There are numerous 'unattainable' pokemon in HGSS that are mostly from either gen 4, or a 'non-wild' pokemon like rotom. There are several that can be found through the PokeWalker courses that unfortunately cannot be accessed since we don't have the physical components to do so. I'm a perfectionist and if I'm going to invest a bunch of time into a Pokemon game, I want to complete the Pokedex.
For the legendary pokemon that you would normally encounter as an overworld sprite, like the regis, I'm assuming that adding their sprites in like that would be a challenge. Especially since you would want to probably add extra hidden rooms or puzzles to get to their 'lair'. I was thinking though that a easier way to get around that would be to make them like a really really rare wild pokemon only in specific areas like Warmech from Final Fantasy. So for say Regice, have him appear only at night with like a 1-2% encounter rate on Basement Floor 3 only in the Ice Path or something like that.