I managed to get my hands on a cheap a copy of a really good fairly old ubisoft game beyond good and evil.
I actually for some reason forgot this game existed. I had it in 2003 when it came out.
When We spoke ages ago about particular games that inspired I said okami, but forgot about beyond good and evil. Regardless it is awesome.
It has a big explorable environment that rivals Zelda. Instead of a horse or boat you get about via hovercraft which means you can go straight from land to sea and buy upgrades to jump into other areas and even fly to the moon later in the game.
Image source http://www.gamershell.com/pc/beyond_good_and_evil/screenshots.html?id=17093
The game starts by literaly throwing you in at the deep end and the story evolves as it goes along without any agonisingly boring cutscenes.
The protagonist jade lives in a lighthouse with her uncle pey'j who is a pig. Her planet is under attack by an alien species called the domz and the first "domz attack" begins immediatley. The alpha sections are the speicial army in the game that protect you from the domz or so you think at first. Early on in the game Jade accidently joins the rebel organization the iris network and fins out what the alphs sections are really up to.
It is one of those games where you have to sneak. Sneak past enemies and avoid being detected. The environment is awesome though and there are many side quests in the game that include taking photographs of animals and collecting pearls to use as payment to upgrade your ship.
9/10 could have been longer.