"There are no tourist attractions in Kigali," Paul from a travel agency in the capital told me soon after I arrived. I wanted to spend time in Kigali so I pressed him for things I should see. "There is a city bus-tour," replied Paul, "which stops at a genocide memorial site, the road where the peacekeepers were shot and the house of the former colonial governor." The three stops on that tour symbolise for me the series of awakenings about history and humanity that shook me in Rwanda.
When I told Paul I was looking for breakfast, he pointed me in the direction of a good croissant in a district called Deux Milles. This is Kigali's Covent Garden, an area of restaurants and small shops selling handmade furniture, organic produce and stationery. Each building is coated in vibrant colours with hand-painted shop logos: a baby pink Harmony Pharmacy, next door to a restaurant called Life Goes On, as if a cry from the street that even the genocide of a decade ago cannot crush the spirit.
For three months in 1994, Rwanda was overwhelmed by organised mass murder: a "final solution" planned by an extremist political faction which generated mindless killing, hatred and devastation among neighbours and friends. Rwandans want people to know what happened in their country. They are pleased that travellers are now visiting, and many want the tourists to see the memorial sites. At Murambi survivors encouraged me to photograph the exhumed bodies on display. "I don't want to hate the people who killed my relatives any more. If I hate I cannot feel the humanity in myself; and I do not want my children to grow up with the heart that I live with," one survivor said to me.
What people are trying to achieve today in Rwanda is awe-inspiring. Neighbours repair the roads together each morning, a small sign of the sense of community that binds the capital. In a world where urbanisation usually involves pollution, traffic, consumerism and crime, Kigali is a model capital, unusual in its combination of the cosmopolitan and the earthy.
The capital has an extraordinary city-scape of houses and banana trees. Urban and rural complement one another: swanky bars pose on top of vegetable plots. At night the sounds of people are drowned out by the frogs. Clean, safe and so small that acquaintances bump into each another constantly, Kigali's streets are passages of elegant greetings. Friends embrace and kiss three times as they meet; even armed soldiers, who maintain the city's security, shake your hand if you approach them for directions, taking hold of their right elbow with their left hand as a way of showing respect.
I visited a friend, Regina, at her house in the hills. It is simply decorated with naked white walls and dark wooden furniture. She tells me that life would not be as good without a glass of fresh milk every day; and by fresh she means delivered each morning straight from a nearby milking parlour.
In Kigali you can hook up to wireless internet in a five-star international hotel; you can eat smoothly pounded West African yam fu-fu, a freshly baked French baguette, or a slap-up Chinese meal; but it is also a city where you are constantly eyed up by a thousand privately owned cows. They are coquettish, with long, fine horns, and they are a lot slimmer than your average Jersey. Cows were Rwanda's traditional currency and still have an important place in life in the capital.
While milk is a big thing in Rwanda, Natural Passion is the drink of the moment, made from passion fruit and created by a young entrepreneur in Rwanda's university city, Butare. Natural Passion also flows in Planet, Kigali's hottest new nightclub. In Planet I experienced my first Kigali chance-reencounter, when I spotted Paul. During gaps between the hip-hop beats I told him how much I was enjoying Kigali, and insisted that he was a terrible PR man for his capital. He laughed and showed me on the dancefloor that if he wanted to pack in his day job, he could.
Rwanda is also one of the few countries in the world where you can see gorillas in the wild. Its national parks are home to monkeys, hippos and crocodiles. But you do not need to go on safari to be dazzled by the countryside; you just need to catch a bus. On any highway, the scene changes with every turn. Banana-trees litter the landscape, their cracked leaves raised skywards as if in an expression of surprise, or song or prayer
We drove into the highlands, where the climate is perfect for tea and coffee cultivation. An important diplomatic duty for the British ambassador to Rwanda used to be to procure some excellent Rwandan tea to take home to the Royal Family. Today the label on packets proclaims it "the best tea in the world". But, while the subtly fragrant black leaves are still rare outside the country, coffee is now one of Rwanda's main exports.
In exchange for sending coffee, Rwanda would like some more tourists. And when they come, Lake Kivu is where they should head to. This is the Great Lakes region of central Africa, and at 2,700 sq km, Lake Kivu is one of the greatest. Its waters have dual nationality: they are shared by Rwanda and the Democratic Republic of the Congo.
For anyone trying to avoid the treacherous currents of conflict that swirl through this part of Africa, Rwanda is the side of choice. One of the provinces that fringe the lake is Kibuye, and it feels strangely similar to Tuscany. Bright greens and yellows emerge from scorching red earth hills under a clear blue sky.
For the tourist, Lake Kivu conjures serenity and peacefulness. The world's oldest stone tools have been found on its shores. And although the sense of the past is heavy here, in Rwanda, like nowhere I have been before, I feel I am in a place that is on the verge of a future.
There are no direct flights between the UK and Rwanda. Kigali is served by Kenya Airways (01784 888 222; www.kenya-airways.com) via Nairobi, or SN Brussels (0870 735 2345; www.flysn.com) via Brussels. BA (0870 850 9850; www.ba.com) flies to Nairobi and Entebbe, where you fly to Kigali on Rwandair Express (00 250 57 57 57; www.rwandair.com).
There are also good budget hotels like Hotel Okapi, Kigali (00 250 571 667; www.okapi.co.rw; B&B from $23/£13) and Kivu Sun, Gysenyi (00 250 54 11 01; www.southernsun.com; B&B from $95/£53). Guesthouse Kibuye is currently closed.
Bradt Guide Rwanda, £13.95.
Rwanda Tourism (00 250 57 65 14; www.rwandatourism.com).