Deviled eggs should always be hard-boiled but be sure to not overcook them. That will help avoid discoloration of the yolk.