My suggestions would be (if you can find them...):
-Luigi's Mansion-feels really fresh. basically a combination of a Mario game, Resident Evil, and Ghost Busters.
-Pikmin 1-also really original. I didn't like the sequel nearly as much. I found it more frustrating and more conventional.
-Eternal Darkness-a true classic in the survival horror genre. One of the very best.
-Starfox Adventures-awesome graphics, and I prefer its gameplay to the modern Zelda games on which it's (sort of) molded. My favorite Rare game to date, and I like it more than Wind Waker, which is my favorite 3D Zelda game to date.
-Fire Emblem-I thought the first Gameboy Advance Fire Emblem was way too hard, but I enjoyed this one more than the vast majority of strategy/RPGs. Surprisingly fun story too.
-Chibi-Robo-gets way too hard later on, but its unique and maybe still worth playing (certainly worth a rental).
-As mentioned, the Zelda compilation discs if you can find them. I was an idiot to sell mine.
-Almost forgot-Beyond Good and Evil! This is probably closest to the Zelda format, though with a lot of differences. I liked it more than Zelda too, just for it's originality and the neat main character. The Gamecube version was one of the better versions too.
I personally wouldn't recommend Super Mario Sunshine as it's WAAAAAAAAY too hard. Halfway through the game it's harder than Super Mario Galaxy is by the end, and I was never able to get more than halfway through. It LOOKS great, but just too hard and not nearly as good as the 2D games IMO. Rent first.
I also personally didn't like any of the racing games. For whatever reason I don't like the Mario Kart games, and Super Smash Bros. has never done much for me either.
-Metal Gear Solid-this remake is inferior to the Playstation original (which is or was actually just rereleased as a compilation), but if you don't own a Playstation 1, 2, or 3, this would be a good game to get. This is actually remade by the developer of Eternal Darkness, and I've always been disappointed they wasted that time remaking someone else's game rather than doing a new original game. A team capable of Eternal Darkness should not be wasting time doing ports.