It is indeed the difference in the games. Paper Mario was designed by Nintendo themselves, who knew how to get the most out of the GC and fit it on to the tiny discs properly. Same goes for other Nintendo games; Super Mario Sunshine still looks incredible, even on a newer TV. Other companies usually had trouble, which is why a lot of the GC releases of multi platform games had blurry textures (due to downsizing the source files) and generally had less features. EA is a notorious example, with the Need for Speed games having quite muddy textures which were then poorly masked by screen filters not found in other versions of the same game.
As others have said, the best course of action is either using an older CRT, or using a smaller TV and upgrading your AV cables. A CRT is the best way, as the games and systems were designed primarily for TVs like that. That said, using an S-Video or SCART lead (the latter being uncommon in the States AFAIK) on a modern flat screen can scrub up an image quite cleanly and gets rid of the blurry look, especially on N64 games. If you have a ridiculous amount of money, you can also upgrade to component cables for the GC... but you can also buy a Wii with component cables and play your GameCube games on that for a quarter of the price of just the cables.