Well, that depends a lot in the computer. Once I made a speed test at 1024x768, it did work well, but when I tried it in another computer (AMD 1.2ghz 256MB RAM) it screwed up.
The Machine-independent speed thing never gave any differences, really.
If you're making a Sonic game, even 800x600 is too much, since the Genesis resolution is 320x224, and the GBA's 240x160.
Unless your graphics are totally custom, you'll have problems due to sizes.
And almost everyone has 1024x768, except for some laptop users or people who uses 800x600 because they can't read well at a high resolution. (In these situations, all the PCs I saw supported 1024x768).