The Tavern offers a list of 5 heroes. To get a famous hero, i.e. one that was advertised in the Hall of Fame, the list may have to be refreshed several times.
Each upgrade level of the Tavern requires you to already have a City Hall at the same upgraded level.
Construction time may vary between players, depending on their Construction Level and Political Points.