For hard mode, there doesn't need to be drastic changes, just a few. Like the Experience Share, I do like that it gives Exp to all Pokemon, although at the expense of overleveling your Pokemon. I think what they can do to make it more challenging is to simply let the EXP Share function like it it did from GSC to BW, just one Pokemon during the main story, and then let it start giving Exp to all your Pokemon after the main game.
Yeah, I also agree that for Gyms, there should be a cap on how many Pokemon we can use depending on how many the gym leader has. Personally, I don't think rivals or anyone need to have a legendary to battle yours. Just make it such that the main Legendary is only catchable post game. Just tweaking the AI a bit to make opponents smarter, such as predicting better switch ins will also work. Oh and finally, yes I agree, let healing only be allowed a maximum of three times per battle.