Rebel leader Joesphy Kony, head of the infamous Lord's Resistance Army, has achieved greater notoriety than any other Ugandan in the world today.
Idi Amin, who ruled the country through most of the 1970s, still stands as a symbol of African dictators who abused power and inflicted gross human rights abuses.
Yet as Uganda prepares to celebrate 50 years of independence next month, the man who has most shaped the country is far less known, at least in the West.
Yoweri Museveni has ruled the East African nation for 26 years, more than half of its post-colonial history. A charismatic former rebel commander, Museveni seized power in 1986, decrying other African leaders who overstayed their welcome.
Museveni points to many achievements in a country with a troubled past. But today, more and more Ugandans say their president has grown heavy-handed as he clings to power.
Despite this criticism, Museveni has dug in his heels. Just before he won a fourth five-year term last year, Museveni changed the constitution to loosen term limits.
In an interview with Al-Jazeera at the time, Museveni was characteristically defiant, deflecting arguments that he had been in power too long.
"The main point is: How would Africa transition from backwardness to modernity?" he told the Qatar-based network. "We should be talking about that, not talking about the individuals. ... Talk about the process of transformation from Third World to First World."
In the Kiseka market, a huge auto parts bazaar in the capital of Kampala, it's said that you can buy everything you need to assemble a Toyota Land Cruiser from scratch, if you want to. Here, the grease-stained shop owners speak their minds.
"I was born in 1986, and all I have to tell you is I have never seen another president," says 26-year-old electrician Jeremiah Senyondo. "All I see is Museveni, Museveni. And what I feel on the inside of me is [the need for] change."
This is a sentiment heard more and more across Uganda: It's time for someone new.
From Freedom Fighter To Autocrat
Museveni sees himself as an aging revolutionary, a historic figure who fought in the bush and overthrew dark forces, and whose mission to transform Uganda is not finished, despite the fact he's been around for a quarter-century and is pushing 70.
No one denies Museveni's accomplishments. Under his long rule, security has improved, the army is more disciplined, and the economy has gained traction.
Today, more children go to school, the fight against HIV/AIDS has made progress, and Washington considers him a key regional partner in fighting terrorists in Somalia.
"Uganda has made great strides," says Ugandan political scientist Frederick Golooba. "But, having said that, I think that we have reached a point where Uganda no longer needs Museveni. Most people would say that."
In Uganda's half-century as a nation, it's no longer enough that Yoweri Museveni overthrew tyrants Idi Amin and Milton Obote.
Museveni was once regarded as one of the most progressive leaders in Africa. Today many Ugandan analysts say Museveni increasingly resembles any other African big man, characterized by vainglory and egocentrism, nepotism and corruption, repression of opposition figures and intolerance of dissent.
"I guess the longer you stay in power the more vulnerable you become," says Daniel Kalinaki, editor of the Daily Monitor newspaper. "I think what we're seeing now is the government entering a phase where regime survival becomes a top priority."
A report released last month by Human Rights Watch, titled Curtailing Criticism, claims the authoritarian climate in Uganda is typified by the president's treatment of certain nongovernmental organizations. The report says groups have recently faced closure, intimidation, arrest and decertification for challenging the government's political and financial interests.
No Tolerance For Dissent
In Kikyusa, a mud-street town where a small nonprofit called the Development and Child Welfare Initiative is staging a civic meeting, villagers pass around a microphone to voice grievances against the government. It is a unique opportunity for the villagers, who are not used to confronting local officials.
One man stands up and faces the stony-faced district police commander, complaining that when he goes to the police department to make a complaint that there's been a crime committed, the officer asks for money to go arrest the suspect, some 20,000 shillings, or $8.
A woman asks who is supposed to pick up the stinking garbage. A hotel owner wants to know why he should pay taxes when the government does so little for this town. One fuming parent wants to know why a rich pineapple grower is allowed to rape local children and then pay off the police to avoid arrest.
These sorts of questions make people in power uncomfortable, and that's the point, says John Segujja, the project coordinator. But it's a project that comes with a cost in Uganda.
Segujja explains that when he went to renew his organization's registration earlier this year, he was told it was under investigation by the president's office.
His group, which is supported by international donors, still has not been recertified. He says the government is blocking recertification because the group encourages people to challenge officials.
"We are opening the peoples' eyes and ears to ask questions," Segujja says. "And people in government don't want to be asked questions, especially on matters concerning corruption."
The president's spokesman did not return NPR's repeated phone calls to comment on this story.
Defense Minister Crispus Kiyonga, a protege of the president's for 26 years, said in an interview that foreign NGOs operate "with anarchy" in Uganda and need more oversight.
When asked about the president's longevity in office, he smiled and said it's up to Ugandans to decide whether they want to keep Museveni in the country's top office when he runs for an expected fifth term in 2016.