I'll assert that Sunshine wasn't non-linear. The game encouraged exploration only in Plaza Delfino (where it encouraged a lot of it. Damn that place was riddled with secrets), but the way the Shines were set up, you couldn't get the Shine that you weren't assigned to get, and the level was often modified to reflect the specific Shine assigned.
Only Super Mario 64 really gave you a sandbox to play around in. There were very few stars that you couldn't get unless you were *assigned* it. I think i can list them, actually: King Bob-omb, King Thwomp, the Koopa the Quick races, the Big Penguin race, the first fight against Big Boo, the Submarine, and capturing the monkey on the mountain.
Those stars were really what Sunshine was like, where unique things appeared based on that. Galaxy of course took that off in a whole new way by more totally modifying the world based on what star you were trying to get, so that aside from thematic concerns, you often might as well not be in the same level.