Avocados are a great fruit to go with eggs. You can try Plantains too. Plantains are starchy and less sweet than bananas. Therefore, they go well with eggs.