There is a process called evolution going on. It's gradual and at some point there was a first bird which had the right gene combination for us to call it a chicken. It's parents did not have this specific traits and hence it's the egg which came first. Not some random "eggs".

We should come up with a better alternative paradoxes ...