Character movement! I never played MP3, but IV, RDR and V were the clunkiest to control games on foot i have ever played. That's something they could DEFINITELY improve on.
As for a specific genre? I really don't know. A racing game or a linear action/stealth game would work well. I actually really wouldn't mind them doing a few more linear games to be fair!