ZSNES is excellent on Linux. Just the same as Windows really. I have Mupen 64, and while it's pretty good, it's certainly due for an overhaul. I use FakeNES for NES games, and have found it to be tremendous.
If you are after a Megadrive/Genesis emu, I recommend
the version of Gens on this page. I'm not altogether sure, but I think you need to have a graphics card for it to work, but it runs beautifully on my Ubuntu 7.04 with a simple Geforce FX5600.
The emu scene on Linux needs a serious update, but these are OK for now. Good luck!