Why did they wait 13 years?
Recorded history is somewhat murky (until the files of the H.W. Bush presidency are unsealed) but there's some evidence the US gov't at the time tried to do it by inciting uprisings. In particular, Bush gave some speeches inciting them, e.g.
on March 1, a day after the end of the Gulf War:
In my own view...the Iraqi people should put [Saddam] aside [...]
On the other hand:
In 1996, Colin Powell, Chairman of the Joint Chiefs of Staff, admitted in his book My American Journey that, while Bush's rhetoric "may have given encouragement to the rebels", "our practical intention was to leave Baghdad enough power to survive as a threat to Iran that remained bitterly hostile toward the United States."
Bush's national security adviser, Brent Scowcroft, told ABC's Peter Jennings "I frankly wished [the uprisings] hadn't happened ... we certainly would have preferred a coup."
So it looks like the US establishment as a whole (at the time) would have preferred a[nother] Baathist in power in Iraq, just one more oriented/focused against Iran.
As the uprisings were put down, H.W. Bush then declared that:
I made clear from the very beginning that it was not an objective of the coalition or the United States to overthrow Saddam Hussein.
I'll take a stab at this, from memory:
The coalition was brought together to eject Iraq from Kuwait. Broadening its goal to remove Saddam after the fact would have "bait and switch". And would have sat badly with some of the Arab participants, like Syria, which were essentially dictatorships themselves.
There was, unlike in 2003 with the more cavalier attitude of the Bush Jr administration, concern that a regional power vacuum would develop and/or that a post-Saddam Iraq would be unpredictable.
Having lost a good proportion of his most loyal troops (the Republican Guards), recently had to exit the ruinous Iran-Iraq War, which he had initiated, and facing rebellions in the North (Kurds) and South (Marsh Arabs) it was felt that Saddam's days were numbered in any case and the Iraqi people would themselves remove him. The no-fly zones were intended to assist this process.
It came IIRC somewhat as a surprise that this did not happen and that he stayed in power.