Yes, it's possible and I'm sure they're out there. I remember playing a megadrive emulator on my old Nokia 6600 (S60), bearing in mind it ran at about 100MHz but still ran at full speed (with frame skip naturally). The N95 should be a lot better, but it's not easy playing with the controls.
Search for PicoDrive, thats probably your best bet. Dont forget Quake and Doom etc, they're all out for the N95.