1) If we're talking through gameplay, it should be hard enough to find that not just anyone can find it, but simple enough that when found, it's seems like anyone could. The recently solved Haunted Adventure Trilogy Ultimate Easter egg comes to mind. If it's a more mechanical Easter egg, I think it should be even more reasonable to find or some sort of hint provided. The paddle game Easter egg on the Flashback 2 makes sense, but only after you know about it.
2) I think it should remain hidden until a player finds it. A good chunk of my interest in homebrews is searching for long lost Easter eggs. It's another reason to pop in an older homebrew; to see if you can solve that last mystery. I bought a couple games from the store for the sole purpose of searching for an Easter egg that remained hidden long after they had been released; Haunted Adventure Trilogy comes to mind.
3) The most fun Easter eggs are hidden games, followed by hidden enhancements to the game, found through playing in a slightly different manner. Pitfall II on the 5200 is a good hybrid example. Though not through gameplay, the one for the 2005 mini game multicart was great. It's a hidden game, you could stumble upon it by accident and might not even realize it, and clues were provided in the form of a poem and in the manual.