To find Epics and Legendaries, there are two sets of conditions that must be met. One depends entirely on the player, the other on the game, but none on RNG nor herd size!

The information contained here was extracted directly from the game's code. The version of the game used is the latest at the time of writing: v1.0.14 (1).

I found this all out while making my mod "Tame Me Maybe" which notifies you when any special animals spawn on a new day and keeps them spawned if the there's a Festival on the day they show up. The mod can be found on Nexus, but feel free to use the guide instead if you don't want to mod. :)

v1.2.0

Added Dodo and Mouflon conditions!
----
v1.1.0

Added Aurochs conditions!
----
v1.0.0

Initial version with conditions for all the base animals in the game.

These are conditions that depend on the player:

For Epics:

• Have tamed at least 4 different variants of the animal
  
• Have tamed at least 8 animals of that kind, regardless of variants

For Legendary:

• Have tamed at least 6 different variants of the animal
  
• Have tamed at least 12 animals of that kind, regardless of variants

The total amount of animals tamed, it can be seen in the Animal section of the Discoveries tab.

In either case, you don't need them all to be living with you! When you tame a new variant the game writes it down and doesn't write it off if you release the animal, and that is what the algorithm checks for.
Careful: The animals show up on your discoveries tab if you have interacted with them by playing the flute at least once, but that is not the same as having tamed them! You need to actually have invited the variants at least once to your farm.
In the end, it is easier to tell if you have tamed each variant if they are on your farm and you probably need them anyways.

Up to you!

If you meet all the player conditions, then you need to wait for the specific days, seasons, weather and years that they appear in. Legendary animals only spawn on the second year or later, for example. They spawn for a day only and will disappear the next day if you haven't started attuning.

These conditions are set, and should not change unless the devs themselves change this in an update. (let's hope not!)

You don't need to mass tame and release animals to "make room" in the herd! Special animals have a spot guaranteed in the herd if their conditions are met, so you can let sleeping Guanacos lie!

Extra info: The Golden Ostrich has a spawn date that is the same as one of the Festivals (4th of Fall), and because both happen in the same area, you can't actually tame them on that day. (You can on the next day with my mod though!) I haven't tested this with all the animals because that would require way more time than I actually have, but I imagine this could happen for others as well.

These conditions are as follows:

------
Bison

Golden Bison: Epic
Conditions:
Days: 3, 17
Seasons: Summer, Winter
Weather: Any
Years: Any

Chicle Bison: Epic
Conditions:
Days: 10, 24
Seasons: Spring, Fall
Weather: Any
Years: Any

Sky Cloud Bison: Legendary
Conditions:
Days: 22
Seasons: Summer, Winter
Weather: Any
Years: Year 2, Year 3, Year 4, Year 5, Year 6 Or Later

------
Junglefowl

Golden Junglefowl: Epic
Conditions:
Days: 6, 20
Seasons: Spring, Fall
Weather: Any
Years: Any

Amethyst Junglefowl: Epic
Conditions:
Days: 13, 27
Seasons: Summer, Winter
Weather: Any
Years: Any

Grand Turquoise Junglefowl: Legendary
Conditions:
Days: 10
Seasons: Spring, Fall
Weather: Any
Years: Year 2, Year 3, Year 4, Year 5, Year 6 Or Later

------
Ostrich

Golden Ostrich: Epic
Conditions:
Days: 4, 18
Seasons: Spring, Fall
Weather: Any
Years: Any

Sapphire Ostrich: Epic
Conditions:
Days: 11, 25
Seasons: Summer, Winter
Weather: Any
Years: Any

Rainbow Ostrich: Legendary
Conditions:
Days: 14
Seasons: Summer, Winter
Weather: Any
Years: Year 2, Year 3, Year 4, Year 5, Year 6 Or Later

------
Ibex

Golden Ibex: Epic
Conditions:
Days: 2, 16
Seasons: Spring, Fall
Weather: Any
Years: Any

Shallow Waters Ibex: Epic
Conditions:
Days: 9, 23
Seasons: Summer, Winter
Weather: Any
Years: Any

Spider Ibex: Legendary
Conditions:
Days: 26
Seasons: Spring, Fall
Weather: Any
Years: Year 2, Year 3, Year 4, Year 5, Year 6 Or Later

------
Wild Boar

Golden Boar: Epic
Conditions:
Days: 1, 15
Seasons: Summer, Winter
Weather: Any
Years: Any

Fiber Boar: Epic
Conditions:
Days: 8, 22
Seasons: Spring, Fall
Weather: Any
Years: Any

Fire Boar: Legendary
Conditions:
Days: 6
Seasons: Summer, Winter
Weather: Any
Years: Year 2, Year 3, Year 4, Year 5, Year 6 Or Later

------
Steppe Horse
Golden Steppe Horse: Epic
Conditions:
Days: 7, 21
Seasons: Summer, Winter
Weather: Any
Years: Any

Cloudy Day Steppe Horse: Epic
Conditions:
Days: 14, 28
Seasons: Spring, Fall
Weather: Any
Years: Any

Starry Night Steppe Horse: Legendary
Conditions:
Days: 18
Seasons: Spring, Fall
Weather: Any
Years: Year 2, Year 3, Year 4, Year 5, Year 6 Or Later

------
Guanaco

Golden Guanaco: Epic
Conditions:
Days: 5, 19
Seasons: Summer, Winter
Weather: Any
Years: Any

Fiery Guanaco: Epic
Conditions:
Days: 12, 26
Seasons: Spring, Fall
Weather: Any
Years: Any

Icy Guanaco: Legendary
Conditions:
Days: 2
Seasons: Spring, Fall
Weather: Any
Years: Year 2, Year 3, Year 4, Year 5, Year 6 Or Later

------
Aurochs

Golden Aurochs: Epic
Conditions:
Days: 7, 21
Seasons: Spring, Fall
Weather: Any
Years: Any

Snow Aurochs: Epic
Conditions:
Days: 14, 28
Seasons: Summer, Winter
Weather: Any
Years: Any

Flame Aurochs: Legendary
Conditions:
Days: 10
Seasons: Summer, Winter
Weather: Any
Years: Any

------
Dodo

Modern Dodo: Epic
Conditions:
Days: 6, 20
Seasons: Spring, Fall
Weather:
Years: Any

Surreal Dodo: Epic
Conditions:
Days: 13, 27
Seasons: Summer, Winter
Weather: Any
Years: All

Pop Dodo: Legendary
Conditions:
Days: 10
Seasons: Spring, Fall
Weather: Any
Years: Year 2 onwards

------
Mouflon

Zither Mouflon: Epic
Conditions:
Days: 2, 16
Seasons: Spring, Fall
Weather: Any
Years: Any

Ukulele Mouflon: Epic
Conditions:
Days: 9, 23
Seasons: Summer, Winter
Weather: Any
Years: Any

Bass Mouflon: Legendary
Conditions:
Days: 26
Seasons: Spring, Fall
Weather: Any
Years: Year 2 onwards

That's it! Pretty simple, huh? No need to mass tame or release, nor keep scouting areas everyday looking for a new spawn.

Like I said before, I haven't tested this with all the animals, but the data comes from the game itself and I haven't found any evidence that these conditions change at any time for any reason, they are hard-coded into the game.

Please do let me know if you weren't able to find an animal on one of the dates listed here. And if you want to be sure and don't mind modding, you can use my Tame Me Maybe mod to get notified about spawns. The notifications fire whenever the game adds them to a herd, so even if the conditions change, it will still fire up on the right days. :)