Metroid and Zelda.
So many hidden puzzles and so much to explore. I find Link and Samus very similar too. I once took a Wavebird at set them at the same frequency and played with Link and Samus at the same time against a friend in Melee. I won.
Anyway, imagine Ganondorf taking over Ridley and using Metroids, or the Space Pirates using the Triforce to try and take over the galaxy.
Samus and Link must team up and you'd have cool mechanics, like energizing Link's sword with Samus's arm canon, or Link throwing Samus in Morph Ball to hard to reach places. Then using items in synergy, like the grapple hook and grapple beam to swing each other across large gaps or restrain enemies.
Goddamn, I really want this game now.