I like larger games that allow you to explore.
Mario (we're talking original ones here) was a very linear game, very little in terms of exploration. However, what little exploration there was was encouraged and rewarded with coins or short cuts.
Sonic, on the other hand, had large maps with often different paths to the end. Unfortunately, time and speed were encouraged, not exploration. Although exploration was occasionally rewarded, you had to be lucky to find the reward. You didn't have time to try to jump against every wall or try every path, unlike Mario where hitting down on every pipe didn't really cost you a lot of time.
This all changed with Mario 3, really: bigger world, bigger levels, the ability to fly: all points that increased the explorationability of the Mario games. And when Mario64 came along, that was it: big huge world with no time limits that greatly encouraged exploration. As I recall, when Sonic made the transition into 3D, it basically went the exact opposite: his games became more linear with less chance to explore. Which was sad, because it was a really pretty game.
