Nuyork,
I wouldn't bother with the Paper mario series. It's really slow and has this fight element somewhat like Final Fantasy - the type that becomes repetitive pretty quickly. Smash, wait, bounce, wait... The riddles are pretty easy but I just couldn't go on after a while. Too boring. Even the special abilities are pretty lame and you can barely every use them. If you're looking for good Gamecube games get Resident Evil 4, Metroid or as you said, Viewtiful Joe. Also, you can get Ikaruga and Soul Blade 2(you can play Link).