This may be just begging for trouble, but I have to say Sonic. When you get down to it, Mario is just a fat old man, whereas Sonic is a fine-tuned athletic machine! (yes mr. coach kline...)
Actually, with the new partnerships between Sega and other companies, we could see Mario and Sonic duke it out later on.