NTSC vs. PAL
Don't run PAL. You can't jump as high or as far.
NES vs. All-Stars
It's important to note that you should not run any high-level serious attempts on All-Stars if you want a truly optimal time; although this version is prettier, and the physics are pretty much identical, there are several elements that are present in the All-Stars version of Super Mario Bros. 3 that don't exist or behave slightly differently than they do in the NES version.
At the beginning of each stage is a "Mario Start!" designation, which wastes 86 frames (1.43 seconds) for each occurrence, which adds up to 2 minutes or more over the course of a warpless run.
Many doors in All-Stars are fancier than their NES counterparts; they have an actual door in the frame, which is animated opening and closing. This is 39 frames (0.65 second) longer than it takes to go through any door in the NES version. In general, the more fortresses you need to clear in your run, the more this will impact it; a typical warpless run wastes at least 9 extra seconds just on longer door animations.
As you fall through the air, for some reason, in All-Stars, it takes longer for Mario to start descending to the throne room. This wastes around 159 frames (2.65 seconds) per occurrence, which means in any warpless run, you waste 18.55 additional seconds to falling through the air.
If you're new, you need to know that playing N-Spade takes positively forever in All-Stars - in the NES version, you can move again the moment you're done flipping a card that matches, but in All-Stars, you're made to sit there and listen to the ding and watch the flashing lights. This wastes 86 frames (1.43 seconds) per match, for a total of 774 frames, or 12.9 seconds, just waiting on fanfares.
But the time taken to flip a card and be able to move on to the next when your cards don't match is longer in All-Stars as well - 5 frames longer. So for flipping 9 cards pre-match, you lose another 45 frames, or 3/4 of a second.
So by the time you're done playing a full game of N-Spade in All-Stars, it's a safe assumption you're wasting 14 to 15 seconds beyond what you'd spend playing it on NES, depending on which pattern you got.