64 did lack a bit on fighters, but it had a few gems. MK4 was decent, I like the n64 MK Trilogy a real lot, too. IMHO, it's better then the psx one because you play more then it loads... just an odd prefrence of mine ;]
MK Anthologys wouldn't be bad, either. Very solid side scroiller.
I remember really enjoying mace the dark age. If you're going after rush, there was a DC version too, which was a good deal prettier (but if you're talking emu only here, that's out of the queston). Mischeif(sp) makers would work good on a cab. You may be able to get away with yoshi's story too.
MMmmm... lots of fond memories. Maby the 64 will get dusted off later tonight