QIf this follower's Last Words ability triggers, and I have no copies of Colosseum on High in my deck, do I still have to search my deck?

AYes. After looking through your deck, you would shuffle it without summoning a Colosseum on High.

QIf I play this follower's Fanfare ability, which player goes first?

AThe active player does. When multiple players need to make a selection, the active player will go first. In this case, the order will be as follows:

1. The active player buries each follower on their field except for one of their choice.
2. The next non-active player buries each follower on their field except for one of their choice. This continues until each player has resolved this follower's Fanfare ability.

QIf an opponent only has 2 Heavenly Aegises on their field, can this follower's Fanfare ability cause them to bury 1 of them?

AYes. Heavenly Aegis's "This follower can't be destroyed by abilities" does not trigger because burying a card isn't the same as destroying it.