Premise: You play as a bird. Could be that you have to live as a bird (i.e hunting for prey, drifting on thermals and timing your attacks on fieldmice etc) but it needs a backdrop.
Setting: medieval wartime (think game of thrones using messenger birds). Survival horror as a carrier pigeon. You are tasked with taking messages from one place to another. You might get shot at with arrows as you leave or arrive bringing news someone doesn't want to be revealed. You can get attacked by hawks or eagles. You have weather elements to contend with, like wind, hail, storms. You need to eat. You need to catch favourable thermal updrafts for high speed travel.
Story is revealed to you as a consequence, either indirectly or directly as a result of your mission success. Deliver one message and an alliance is formed, changing the course of war. Fail to reach it on time and the alliance fails, shifting the power balance of several factions.
Like Chibi Robo, where you see a family dynamic change as their life is made easier by your actions in cleaning up the house, you also have expository dialogue of sorts. You get to hear the musings of people who receive your messages. You can choose whether to deliver it or not along the way, or accidentally go to the wrong place.
Gameplay conceits could work well: pigeons have excellent navigation skills to allow for a GTA style radar map.
And if you get really bored you can shit on people's heads via a dedicated button. Wii U control pad screen would serve as an excellent perspective for "bombing runs" down busy streets.
For "stealth missions", how about high profile poop targets on the heads of VIPs, or evading a particularly vicious predator like a peregrine falcon by flying through a heavily forested area and making mad dashes across open plains. Or retreiving a key or something that you know someone wants/needs.
You could also chill out and fly around the landscape, Crackdown style trying to reach the tops of mountain ranges a la Agency Tower, or just explore nooks and crannies of woods and shit seeing people in small bands of thieves or farms etc interacting.
