Sonic and Mario... no, it would be terrible. Their worlds are just too different. Mario has all it's bright colours and hills with eyes... and Sonic has a more realistic environment... I just can't see how it would work.
Sonic seems to be aimed at a slightly older audience than Mario... they'd work together okay in a SSBM style game, but anything else, I'm sorry, would suck.
I'll be honest and say I'd like to see more Mario games set in less bubbly environments... We get hints that the Mushroom Kingdom has huge cities in the GB Donkey Kong game, Mario Kart series and the Wario Land games.
I'd say Mario Sunshine was a big step forward from Mario games environment-wise... and then Mario Kart: Double Dash!! was a step back.
There were a few courses in that game with scenery that would have looked more at home in Kirby Air Ride. Mostly because they felt the need to put eyes on almost EVERYTHING. If I remember correctly, you can even see eyes on the sun if you look closely through the glare.