I'm not sure if they count as Easter Eggs, but the multiple different paths and special endings included in Kiel_Farran's 'A Game of Life and Death' were what kept me coming back to the game and replaying it over and over. The promise of hidden epilogues made me really pay attention to every detail and explore every corner of the game in hopes of finding something new.
That's the point of including Easter eggs and side quests, imho, to keep the players engaged. So your best bet is to include a few fairly obvious Easter Eggs to let the players know that they're there and a few not-so-obvious ones that are there for the player determined to figure out every inch of the game. Probably one every couple pages is enough to keep the players reading carefully if they want to find them.
Side quests are probably a lot of work, so I think an optional one every few chapters is more than enough, depending on how elaborate they are.
I'm of the opinion that you can never have too much optional content, but the amount of effort it would take to make it would be insane, so I guess it comes down to how much effort you want to invest in something that's not really crucial to the story itself.
That's my two cents, anyway.