- Orshabaal and Yeti were introduced in 7.4 - https://tibia.fandom.com/wiki/Orshabaal ; https://tibia.fandom.com/wiki/Yeti - December 2004
- Major change happened in update 7.5- https://tibia.fandom.com/wiki/Updates/7.5#New_Bosses - Update was In August 2005 and as per Tibiawiki New type of the bosses has been introduced, such as:
- General Murius
- The Evil Eye
- The Horned Fox
- The Old Widow
However, there is possibility that they have been introduced earlier in December 2004 as I found an article on Tibia.com https://www.tibia.com/news/?subtopic=newsarchive&id=317&fbegind=3&fbeginm=4&fbeginy=2003&fendd=3&fendm=5&fendy=2006&flist=11111111
"ome time ago a new category of monsters has been introduced to Tibia. These so called boss monsters are unique and very strong. We would like to invite you to participate in the new voting, which deals with this topic."
As much as it is possible, this can also be related to Yeti and Oshabaal from 7.4 also Pharaohs which been introduced in Summer updated 2004 (August) https://tibia.fandom.com/wiki/Updates/7.3- but those are Quests bosses.
The first "rare spawn" boss was Orshabaal implemented in 7.4 update on December 14th, 2004.
The next bosses to be added were in 7.5 on August 9th, 2005. They were:
Introducing the ability to bump and pin questionsJanuary 09, 2022
Fourth Anniversary InfographicDecember 30, 2021
Interview with Laethye - Game Content Designer of TibiaNovember 23, 2021