100% Yes on flying!
Flying's more fun than running, swimming, crawling, rolling, jumping or driving.
Banjo-Kazooie, you learned to fly unusually early on in the game, but it was such a major mechanic, it made sense. As flying in games goes, it was slow though. Flying as the bee in Click Clock Wood was amazing! Loved it!(and maybe wouldn't have been so much fun if flying as Banjo & Kazooie hadn't been so slow). Being able to fly as Kazooie in Banjo-Tooie was better without Banjo weighing you down. But having learned it so early on in BK, it was frustrating to learn it so late in BT. Gliding wasn't much compensation.
Being able to fly around the hub world in Diddy Kong Racing was great because it was fast and you could explore. Can't remember whether you could use a plane from the very start though.
Mario's wing cap in Super Mario 64 was good as you could dive to gain speed, but essentially it was just gliding as you had no way to generate height. Also, it was on a time-limit. His flight in Super Mario Galaxy was fun, but was introduced way to late in the game to really enjoy.
If there is going to be flying in Project Ukulele, I'd love it to be similar to exploring New York City in LEGO Marvel Super Heroes. It was fast, easy to control, you could do it as a number of characters and it was just fun to be given such a large area that you could just bowl around in!