Super Mario Galaxy would get my vote. But if you did not like Super Mario 64 than it makes the decision a little harder. SMG has really good graphics, is fun to play, doesn't abuse the use of the remote, and is a big step up from Mario Sunshine. But I have had every Mario game since the original NES so I am a bit biased.
I got Super Paper Mario on the 21st of October. I played a bit, 20 hours, and got to the final stages. I was going to get Galaxy as soon as it came out, the 29th of October. I tried to finish SPM in time for Galaxy's arrival but I couldn't. Now that I've played Galaxy, I can't see myself returning to SPM for a long while. Galaxy is superior.