The world swooned as the great man was sworn in as president a few days later and the white generals, who had built a fearsome military and battled across the hinterland of southern Africa to avoid this day, turned to salute him. True, the ideal of the "rainbow nation" was more a vision than an expectation, some might say a self delusion, given South Africa's knotty mix of race and history. Yet the belief and hope of those years was contagious and the infection spread across Africa.
But running in parallel were the worst of times. Weeks after watching Mandela vote, I was standing at a church among thousands of corpses rising from the ground. It was about 3am and I had just listened to a small group of nuns in the Rwandan town of Kibuye describe the massacre of thousands of Tutsis in the Roman Catholic church. Eleven thousand died there in a single day. Another 10,000 were murdered in the football stadium the next.
The bodies were swiftly buried around the church but rains washed the soil away, and everywhere the remains of people frozen in futile defence against bullets and machetes were emerging from the soil. Women, children, old men - no one was spared, not even the priest. Bullet holes speckled the church's corrugated iron roof. In the backrooms, bloody handprints adorned the walls.
I had met the man responsible for all this a few hours earlier. Clément Kayishema was a doctor and, at one time, head of the local hospital, but by the time of the genocide he was a political force as the governor of Kibuye province. When I turned up in his town, he directed that I be held in a hotel-turned-barracks. One day he would have cause to regret that.
I had arrived in Africa four years earlier, not really knowing what to expect. As I was growing up in the 70s, news from Africa was dominated by Idi Amin and Ian Smith, whose stand for white rule in Rhodesia was amply justified in my parents' eyes by Uganda's bloody tyrant. Anti-apartheid boycotts were beginning to take hold, even if there was still widespread sympathy in Britain for the white regime in Pretoria. The mood hardened with the beginning of the Soweto uprising and the state's brutal response a few years later. The long war in Angola was brought to our living room principally through the trial of British mercenaries, as Washington and Moscow fought out their cold war at the cost of African lives. It was only about a decade after independence for most countries, but already the continent was being written off as a basket case run by buffoons and thieves.
That was then. I was landing in 1990 in what promised to be a very different Africa. Alongside the fall of apartheid, the talk was of a "new breed" of African leaders rejecting corrupt, authoritarian one-party regimes preying on their own people. Britain was flinging money at Uganda's new ruler, Yoweri Museveni - a paragon of leadership compared with Amin - who promised not only clean, accountable government but adherence to the prevailing western orthodoxy of privatisation and free markets. Other great hopes would follow: Ethiopia's Meles Zenawi and Rwanda's Paul Kagame.
The expectation infecting South Africa was creeping north, sometimes forcing out the old but always bringing some kind of change. People turned out in their tens of millions to vote, waiting in lines for hours in Zambia, Angola, Malawi, Nigeria, Zimbabwe with enthusiasm and humour for the chance, at last, to have a say in who governed them. They spoke of a new era, an end to war, corruption and the oppressive "presidents for life" who claimed the right to rule perpetually because they had liberated their countries from colonial subjugation. Promise was all around.
But then the new breed often turned out to be like the old breed, and the old breed clung on for dear life where it could. Angola was flung back into war.
Nigeria's army didn't like the election result and imposed its most brutal dictatorship to date. The new rulers of Zambia and Malawi proved to be as corrupt as their predecessors. In Zimbabwe, the first election that posed a threat to president Robert Mugabe's power marked the beginning of a decade of decline and bloodshed that is still frustrating the will of its people.
Calamitous failures of leadership left millions dead and perpetuated the struggle for existence of millions more. Even South Africa, where the courage of FW de Klerk and Mandela had seen a nation reborn, watched its new democracy eroded by the authoritarian and sometimes paranoid leadership of president Thabo Mbeki.
Books have been filled with the shortcomings of African leaders since independence, from the corrupt "big men" and military rulers propped up by the west because of their anti-communist credentials to the former Marxist leaders who wallow in the money they made selling off the state assets they once seized in the name of the people. Yet, after two decades of watching failed leadership, the Africans that have made the greatest impression on me are the extraordinary individuals who stood against that tide.
In South Africa there is Zackie Achmat, an HIV-positive gay Muslim man of Indian extraction and ANC member, who led the campaign against Mbeki's perverted denial of life-saving anti-Aids drugs to poor black people. In doing so, Achmat did much to keep democratic accountability alive under governments that have badly subverted the institutions of the country's new democracy, particularly the judiciary, while corruption flourishes.
Other names are less well known, such as those of the women in eastern Congo who venture into the most dangerous areas to rescue other women from years of systematic mass rape by the gangs of armed militias that amount to the only form of authority over vast territories. Or the Nigerian journalists who risked assassination or long sentences in hellish prisons to expose the truth about the military dictators plundering their country. Not a few were murdered or slung in jail by military courts.
And there are those who names cannot, for now, be revealed. They include the Zimbabwean doctors who have for years lived with the risk of arrest, torture and even death to run an underground railroad to help the victims of Mugabe's sustained and bloody terror against his people. Thousands of the beaten and near-dead have been rescued and spirited to private clinics, secretly operated on and kept beyond the clutches of the intelligence organisations.
Sometimes whole groups of people proved heroic in their own way. White South Africans, particularly the all-too-often vilified Afrikaners, set aside fear and years of indoctrination to support the transition to black rule in a referendum. It was a huge leap of faith - albeit one made in part out of desperation at the realisation that their country was otherwise headed for the abyss.
But of all the silent heroes, perhaps none was more unusual than Sosthene Niyitegeka. The Hutu shopkeeper and pastor risked everything - his own life and that of his wife and children - to save every Tutsi in his village at the height of the Rwandan genocide, with a plan that mixed appeals to human decency with blackmail and infiltration of the militia leading the killing. Niyitegaka's story is extraordinary because Rwanda stands apart. There have been plenty of other mass graves across those two decades and before. But Rwanda left a different mark. It offered the darkest insight into the fragility of society, and it is the legacy of that tiny country's genocide and its tragic failures of leadership that a good part of Africa continues to live with today.
My encounter with Clément Kayishema in Kibuye was brief. He happened to be in the main square when I arrived and he asked what I was doing there. I tried to fob him off with something about assessing the refugee situation, but he ordered some soldiers to hold me in a crumbling lakeside hotel taken over by the army. The soldiers drank through the evening and passed out.
I slipped away in the night to talk to the nuns, who recounted in detail the events at the church. They told of the mobs armed with machetes, grenades and guns, and how Kayishema had told the priest to walk away or die. Then he led the massacre, wielding a sword. Those who survived the initial onslaught of explosives and bullets were hacked to death or lined up and clubbed one by one. Some of the women were gang raped and had their eyes gouged out. Many of the killers were from the town. The nuns recognised them: teachers, civil servants, policemen, peasant farmers.
After three hours of listening to the nuns, I made my way to the church to see first-hand the evidence and then get out of town before dawn. My four-hour drive to the Zaire border was dotted with roadblocks manned by Hutu militiamen with clubs, machetes and guns; but by then most of the Tutsis were dead, so they were usually more drunk than menacing.
I was back in Kibuye a couple of weeks later. It was a Sunday and the people were shuffling into the church, neat in their best clothes. Someone had tried to scrub the place clean, but the smell of the torrent of blood that seemed to have worked its way under the very skin of the church was still unbearable, and worshippers prayed with cloths held to their faces.
The church had a new Hutu priest. He was available because he had overseen the bulldozing of his former church in another part of Rwanda, with its Tutsi congregation still inside. The priest made no mention of the dead. Some of the worshippers denied there had been a massacre; a woman who said it was all a lie refused to look at a foot sticking out of the ground beside her.
Rwanda was about as catastrophic a failure of leadership as Africa has seen. The genocide has been explained away as the unleashing of ancient ethnic hatreds and the legacy of the European colonial obsession with the spurious science of racial hierarchy, which in this case regarded Tutsis as genetically superior to Hutus. All of that played a role, but the unleashing of what was intended to be the final solution to the "Tutsi problem" was a raw power-play by an educated elite that feared losing control to democracy and power-sharing with Tutsi rebels. An entire government, military and a large part of the population was organised to hunt down and murder hundreds of thousands of people, which they did with remarkable success by killing close to a million in 100 days.
In the following weeks, as the government of murderers retreated in the face of a rebel onslaught, the prime minister, Jean Kambanda, told me how the Tutsis had brought it on themselves. The chief of staff in the defence ministry, Théoneste Bagosora, the architect of the slaughter, attempted to portray the mass murder as a spontaneous bloodletting born of fear and anger that no one could stop.
I met Bagosora a few times, but it was only a few weeks after the genocide that I sat down to talk to him properly. He was in Zaire along with about a million other Hutus who had fled defeat. Perched on his chair, a satellite phone at his side and flashing gold jewellery, Bagosora was unapologetic, belligerent and conflicted. On the one hand he was clearly pleased with his handiwork in organising the slaughter of about 800,000 people. On the other, he needed to maintain the fiction that the killings were a spontaneous outburst of anger against Tutsis. So he settled for questioning that it had happened at all.
"People say Bagosora did this or that, that I have the blood of the Tutsis on my hands. But where are all these people who were killed? If they died it is because they are rebels or because the people were angry with them. They didn't need Bagosora to tell them who to kill," he said. "But it's true that the Tutsis are trouble. Now they have taken over the country, a Hutu country. We will fight them again until all the Tutsis are gone."
Bagosora was a cold, frightening figure. The head of the UN mission to Rwanda described meeting him as like shaking the hand of the devil. Yet, like others who have wielded so much power of life and death, he might in different circumstances have been mistaken for a lowly civil servant.
Out of all this also came Sosthene Niyitegeka. The Hutu, Seventh-day Adventist preacher had a small shop, a wife and nine children to protect. But he saw what was about to occur with moral clarity as the Hutu militia, headed by the village primary school teacher, handed out crate-loads of grenades "like sweets", as Niyitegeka put it.
When a Tutsi woman, a nurse with her children in tow, knocked on his door he let her in. A day or two later there was another woman on his doorstep. She had been stripped naked, carved up by machete and had nearly lost her arms.
Niyitegeka's reputation drew others - businessmen, civil servants, peasants - to his house. "They were the kind of people that, if you hid them, you could get yourself killed for. Some were really desperate. Running by night, hiding by day," he said.
After 10 days he was sheltering 104 people in his house and the maize field out the back. But members of the the Hutu extremist militia, known as the Interahamwe, were watching, and Niyitegeka knew he had to find better hiding places. He appealed to those neighbours he trusted to do the decent thing.
Others weren't so co-operative, but the preacher knew a thing or two about who was sleeping with who - the kind of thing that makes people co-operative. In a daring move, he sent people he trusted to drink in the bar where the militiamen tanked themselves up on beer before beginning their hunt for human victims.
The spies sent back word and, over the following weeks, a sinister form of hide-and-seek unfolded as Niyitegeka moved Tutsis between about 30 houses, always keeping one step ahead of the Interahamwe. Sometimes dozens at a time were hurried into the maize fields or the hills as the militia hunted their quarry.
At one point, Niyitegeka persuaded the local council that the militia members were always drunk and thieving from people's houses, and should not be entrusted with the search for Tutsis. So the council appointed the pastor to lead it, and he appointed a group of friends who were hiding Tutsis to help him. When the rebels arrived and the Interahamwe fled, every Tutsi hidden by Niyitegeka was still alive.
Most Hutus did not take a direct role in the genocide. Many passively opposed the murder of their Tutsi friends and neighbours. But only a few actively resisted it. I asked Niyitegeka why he did it.
"Any person could see this was wrong. How could killing children be right? How could it be right to kill the neighbours you have lived with all your life? But Rwanda is a strange country. People do things because the government tells them to. They do not think for themselves. When these leaders say: 'Kill your neighbours while we get rich,' they do not think that is wrong.'"
I had much the same discussion with another Hutu. Theoneste Nzigiyimana was a bank cashier. A badly battered woman who had been raped and beaten, Madalena Mukariemeria, stepped up to the counter. Behind her was a Hutu militiaman, and Nzigiyimana quickly realised the woman's life depended on her being able to give the armed man money. The cashier looked at Mukariemeria's account and it was virtually empty. So Nzigiyimana withdrew 20,000 francs - just £30 but a large amount in Rwanda at the time - from his own account and handed it to the woman.
In the coming weeks, Nzigiyimana handed over a lot more cash, then took out loans when his own money ran out to help save 10 Tutsis and their families. This at a time where mobs of armed militia were terrorising the population and butchering anyone who helped Tutsis.
"I was seeing the leadership was doing things that weren't good, so in my heart I knew it was wrong," he told me. "These are people we used to share things with, living together, marrying each other, working together."
Rwanda left its mark on everyone, Hutus and Tutsis, peacekeepers and aid workers. Reporters too. I agreed to testify against Kayishema, the governor who organised the massacres in Kibuye, at the international tribunal for Rwanda. The prosecution wanted me for one small thing: to establish that he continued to wield authority at a time when he claimed to have been stripped of power.
There is a debate among reporters over whether we should take the stand at international courts, but it seemed difficult to me, after writing of the blood on the hands of western leaders for abandoning the Tutsis, to then refuse to make a small contribution to what little justice there was for the dead and survivors. Kayishema is serving life in a prison in Mali.
The international tribunal has done a good job of capturing and trying those responsible. Bagosora, the mastermind of the genocide, was convicted and jailed for life along with many of the military and political leaders who oversaw the slaughter. But the trials were protracted and seemed distant to the survivors and those rebuilding their lives.
The Rwandan government came at it differently. A few months after testifying at the international tribunal, I watched three men and a woman tied to wooden posts and shot in public in a Kigali stadium for their role in the genocide. Another 18 people were executed on hilltops across the country before crowds of taunting and cheering survivors. The executions were widely condemned. Some recoiled at the medieval practice of killing people in front of a baying crowd. Amnesty International said they would do nothing for reconciliation in Rwanda. That wasn't the point. Almost no one had apologised for the genocide. The only regret among those who organised it was that they had failed to carry through the extermination of the Tutsis. In the absence of remorse, the survivors wanted a price to be exacted for the destruction of their families. It was hard not to agree with them.
I watched one of those hauled before the firing squad with particular interest.
Froduald Karamira was the leader of a Hutu extremist faction whose call to murder pounded across the airways at the height of the genocide. That he was a Tutsi who reinvented himself as a Hutu and became a fanatic to prove his loyalty only added to the horror. When he wasn't on the radio, Karamira was on the streets killing by example.
I met Karamira a few times and sat through his trial on a wooden bench behind him at a packed and dilapidated old court in Kigali. For three days, he again fascinated and appalled Rwandans with a performance that swung from defiant denial of reality to a taunting of the court, all of it broadcast on the radio. He knew he would be shot, and told the judges he would be happy to die if it made the Tutsis happy.
But the bravado fell away as the witnesses spoke. One listed all the members of his family murdered at Karamira's behest. They included his wife, five children, mother, four sisters and two nephews. I spoke to Karamira some time later in prison. He didn't regret a thing.
He was shot in the stadium in which he had led many rallies denouncing Tutsis, and from which he made some of his radio broadcasts. His execution left me cold. As I thought back on the immense suffering caused by Karamira and his cohorts - the slow tortured deaths by machete, the pain of the Tutsi orphans who could barely comprehend what had happened, the women murdered slowly after they were gang-raped and infected with HIV - my long-held view that the death penalty was wrong, no matter what, fell away. Before Rwanda, I could not have imagined saying this, but I would not have saved Karamira even if it had been in my power. I looked at him and believed he deserved to die.
The genocide, though, proved to be just a beginning. Two million Hutus fled Rwanda as the Tutsi rebels seized power. Tens of thousands died of cholera on a hellish landscape of volcanic rock in Goma, as the sky darkened with ash. It smacked of divine retribution, except that so many of the dead were children.
Africa is still living with the legacy 15 years later. What began as civil strife in a tiny country reverberated across central Africa, bringing down one of the continent's longest standing dictators, Mobutu Sese Seko, and drawing a host of countries into the subsequent wars in the Democratic Republic of Congo. Millions died in the perpetual conflict that followed.
Rwanda had other consequences, too. Guilt over the west's failure to act prompted the British intervention in Sierra Leone that put an end to its rebel war and horrific crimes against civilians. Rwanda went on to become a regional power of note, drawing parallels with Israel as a country driven to fight by the need to survive. But the killing and dying in eastern Congo continues on a terrible scale, throwing up difficult questions about one of the most complex and interesting African leaders of these times, Rwanda's president Paul Kagame - for some in the west, the great new hope for Africa.
The former Tutsi rebel leader who ended the genocide has been heralded as the Abraham Lincoln of Africa, a visionary dragging Rwanda away from ethnic politics and dependency on foreign aid. But Kagame has also been condemned as bloodthirsty tyrant, whose army has exploited western guilt to suppress political opposition at home and allow his army to murder and plunder its way through Congo.
The Rwandan leader is intelligent, articulate and hardened by a streak of ruthlessness. He has a better grasp of reality than many of Africa's power brokers. At home, Kagame has embarked on the ambitious project to change the way a nation thinks about itself. As one official put it to me, Rwandans are like steel; they were bent to think one way about Hutus and Tutsis for 40 years and now they have to be bent back. But if it's done too hard or too fast, they will break.
Kagame also seems determined to shift his country away from its historic dependence on foreign aid, with imaginative schemes to turn it into the IT hub of central Africa. There has, quietly, been plenty of vengeance for the genocide over the years - but the state has also sought to rehabilitate and reconcile as it grapples with the reality that it does not have the resources to try and imprison all of the guilty. And yet it sometimes seems that the survivors are marginalised and looked down upon by this new English-speaking Tutsi elite, which grew up in exile in neighbouring Uganda and came back to take over a country.
Across Rwanda's border with Congo, it is another matter. Kagame's army has as much blood on its hands as any of the myriad of armed groups that have killed and plundered their way through that desperate, vast country. For years the Rwandans got away with it, but the perpetual suffering of the Congolese has begun to erode the moral authority bestowed on Rwanda's leadership by the genocide. Still, Kagame is viewed by many, including his friend Tony Blair, as the hope for the future. He may be. Or he may just be another desperate attempt by the west to latch on to a leader with promise.
Where almost no one looks for moral example any more is South Africa.
Mandela's legacy was squandered over the years, sometimes through the realpolitik of international relations but, more disturbingly, by the authoritarian tendencies of his successor, Thabo Mbeki. Mbeki took over the presidency in 1999, offering the vision of an African renaissance that would not only change how Africa was governed, and the relationship between the people and their rulers, but how the rest of the world saw the continent. South Africa by then had the most progressive constitution in the world, even though Mandela was initially none too happy about the entrenching of gay rights.
A decade later, Mbeki's failed leadership is principally remembered for sacrificing the lives of hundreds of thousands of people while he fiddled around in league with a group of maverick scientists who questioned the causes of Aids and the established methods of keeping HIV-positive people alive. Mbeki's blocking of the life-saving drugs to millions of people was his greatest crime, but his stature was further eroded abroad by his malign manipulation of Zimbabwe's political crisis to help keep Mugabe in power. When he wasn't squandering South Africa's moral authority over Zimbabwe, Mandela's successor was wasting it at the UN security council protecting Burma's military regime.
South Africans have other concerns too, principally Mbeki's legacy of a self-enriching, authoritarian and sometimes corrupt ruling elite, and his undermining of the institutions of South Africa's new democracy to pursue his political enemies and protect friends such as the country's police chief, who was consorting with, and probably taking money from, the mafia and trying to cover up a murder.
Through it all, there has been a steady rise in corruption amid a shameless pursuit of money by political leaders who equate wealth with liberation. As Mbeki's former spokesman, Smuts Ngonyama, famously put it, he himself "didn't join the struggle to stay poor".
It's an uphill task to persuade South Africans that the ANC isn't soft on corruption when the party is putting so much energy into keeping its leader and candidate in April's presidential election, Jacob Zuma, from going on trial for bribery and racketeering. The ANC is shameless in its tolerance of corrupt officials. When Tony Yengeni, the party's former parliamentary chief whip, was convicted of fraud as part of an arms deal, he was carried to the prison gates on the shoulders of ANC officials as if he were a hero.
Among those on hand to cheer him was Baleka Mbete, now South Africa's deputy president. The authorities saw to it that Yengeni served just three months of his three-year sentence, and he is again serving in the highest echelons of the party.
The ANC's answer to an array of revelations of corruption in its ranks has been to abolish the independent investigations unit that brought the prosecutions against Zuma, Yengeni and others. Yet in the midst of these spreading abuses, courageous voices stand out again. A lot more lives would have been lost, and democracy corroded even further, if it hadn't been for a courageous collection of South Africans who struggled against apartheid, but who were prepared to break a taboo and criticise the liberation movement.
Zackie Achmat and his Treatment Action Campaign spoke up for those doomed by Mbeki's Aids policies: poor and working-class black people. Their vigorous agitation, on the streets, through the unions and in the courts, held Mbeki and the ANC up to the light of public scrutiny and accountability in a way that had not happened before. Mbeki's ludicrous pronouncements were ridiculed, his lies challenged, his misrepresentation of statistics exposed. Achmat won the day in the courts, and forced the government to supply the life-saving drugs. But they achieved more than that. They opened the door to other legitimate criticisms of the ANC government, particularly on economic policy and the abuse of power; criticisms that a few years earlier might have been regarded as a betrayal of the liberation struggle. This in turn may have gone a long way to rescuing South African democracy, and it's a trend being seen in other parts of Africa, too. The "big men" failed. The new breed was a letdown.
There is, however, plenty of reason for continued caution. The African Union instinctively leapt to the defence of Sudan's president after he was indicted as a war criminal, and it has just elected the repressive and murderous Libyan leader, Muammar Gaddafi, as its chairman.
It says a lot about the state of the continent's leadership that the world's biggest cash prize, millions of dollars offered by a Sudanese-born British telecommunications entrepreneur, is given to African leaders for giving up office without plundering the national coffers. It is, essentially, a reward for following their constitutional duty.
But perhaps now, bad leaders will matter less than in the past. The growth of civil society, a broader and more critical media, access to the wider world through satellite television, the web and mobile phones, and even, in some cases, privatisation of the economy, are laying the ground for what has so often been lacking in the past. A younger generation is more willing to challenge and demand that governments do what they are elected to do. There are a rising number of voices willing to say no to what is wrong.
But I fear it will take another 20 years to realise the fruits of all that.
• Chris McGreal starts work as the Guardian's new Washington correspondent next week. The Guardian's new Africa correspondent is to be David Smith, at present a senior reporter on the Observer