You have LBP, but neither of the New Super Mario Bros (on the DS, or on your list)? NSMBWii is by far better than galaxy. I've beaten NSMBWii like 6-7 times already, and only managed to beat galaxy twice. Since you claim you won't pay full price, and you haven't played a lot of games, buy Super Mario World (or Super Mario Bros 3) on the Virtual Console, and if you enjoy those, you'll love NSMBWii.
anyways,
The Godfather: The Blackhand edition - sandbox type game (GTA style) only with some of the best, most immersing motion controls on the Wii (still to this day). You'll have to find it used, but it was a lot of fun to play.
Mario Strikers Charged - One of the best online and local multiplayer games available on the Wii. I don't know if a lot of people play online any more, but if you have any friends it works flawlessly.
For GC any of these games are great (I'm having a hard time matching up to your library though, so take them as you will)
Pikmen 1 & 2 - they have remakes on Wii, so buy whichever is cheaper. Great game where you control hoards of pikmen to find items and do battle.
Tales of Symphonia - good action RPG. I had a lot of fun with the active battle system.
Fire Emblem: Path of Radiance - if you really love hard strategy games, then get this before Fire Emblem: Radiant Dawn. If you aren't sure you'll like the series, then Radiant Dawn is easier to find, and the better game.
Paper Mario: The Thousand Year Door - good RPG. Uses A/B buttons for attack/defense boost. So you don't just choose what you want to do, you have to make it execute well too. There is also crowd interaction during battles, which makes it more interesting. Not a hard game, but it has a few really good challenges.