As @mickeyknox said, Zhar the Mad is always there on Labyrinth Level 8. In fact, all of the Unique Bosses from the original Diablo are always on their respective Levels.
Many of the other Bosses are random spawns and may take several runs through the Labyrinth. If you would like to see the Levels they spawn on, see this list: Protector of Tristram.
(UA is an acronym for the Unholy Altar Level).
Good luck and good hunting! 