Another game I never really hear mentioned is Rocket: Robot on Wheels for the N64.
It is probably the closets thing to the Banjo games, even more than Mario 64 or anything.
It has a similar structure to BK, you have (I think) 6 levels that are connected through a hub world. You have 12 tokens (like Jiggies) and 250 coins (like notes) to collect on all of them. And they stay collected if you die, just like in Tooie. And you have to learn new moves to get to new levels.
And the most revolutionary thing for a game released in 1999, on the N64, there are Physics-based puzzles, drivable vehicles ( but not like Nuts and Bolts

), a rollercoaster that you can customize and ride and many other things. The levels are at least as big as the ones in Banjo Tooie and contain many secrets to find
And it was made by the guys who made the Sly and Infamous games.