PAL as in.. The European standard of 50 hz versus the NTSC standard of 60 hz.
Basically... one (PAL) refreshed less than the other (NTSC) and should in allow for slightly higher resolutions...
The text in Super Mario 64 PAL version shows up very badly... The way you describe it in fact...
A good tool to use is GoodN64 to rename your roms, and see what region you have. USA and Japanese roms are the only ones that are NTSC (not too confident in this... but... I'll leave other members to correct me if i'm wrong )
I'm not 100% sure but i think that all europe roms are PAL and the rest NTSC.
Anyway, look for (U) or (E) in the filename. If it's (E) then it's pal. Then the advice is to live with it or get another rom.