RPGs: Dark Falz in Phantasy Star 2, the last Dharma Shrine boss in Dragon Quest 7 (please, don't make me laugh by mentioning FF bosses. the only way Square can make them "hard" is to give them instant-kill moves where 1-2 overlooked abilities will make them a complete wuss).
Shooters: Gradius 3's Stage 3 boss. It's not impossible, but I find he's damn hard, harder than any other boss in the game.
Fighters: Nightmare, on the hardest difficulty, is a pain. But Cervantes in Soul Edge was more of a pain. Well, anyway, there's also the aforementioned SNK bosses.