Out of this World
And OddWorld
Or I could go with another of my favorite game perspectives, the isometric view. This has been used in games like Metal Gear Solid and Vagrant Story. It gives an above the character view and is more condusive to non linear exploration.
Metal Gear Solid
Vagrant Story
Now based on the camera perspective I use, the gameplay will likely have to change.
If I go with the side scrolling camera, gameplay will be very based on platforming (jumping to different areas) and lock and key puzzles which will require pulling switches to open doors or move obsticles. Bacially the gameplay of Out of this World or Oddworld Abe's Oddysee
If I go with the isometric perspective I imagine the game to be much more maze like and exploration based. All interactions with enemies would be about stealth and avoidance.
I would love to hear suggestions in the comments!