"Sit, sit," said the waiter, ushering us to a corner of the terrace and sending his colleagues away for linen. Within seconds a new table was being squeezed in between the other diners. The couple next to us were shifted along, even though they were in the process of choosing their dinner from a plate groaning with raw fish that included a huge waving lobster. The staff were all smiles as they chatted with Laura, asking her how she was feeling and patting her belly. Even though it was still over four months to the birth, our baby was the most popular customer in the restaurant.
My wife and I had chosen to spend our last holiday before the birth of our first child in Gozo. We'd been burning the candle at both ends in the run up to the new arrival, and Laura was almost at the point where she couldn't fly, so this sleepy little rock seemed perfect. All we wanted was some relaxation with a bit of sea and sun thrown in - Ibiza would have to wait for another year.
Even before our VIP treatment in the restaurant, the holiday had got off to a good start. The villa that would be home for our first week was beautiful. It sat on the edge of a deep gorge and had clear views over a valley, the island's capital city and its tallest man-made structure, the huge cathedral in the village of Xewkija. To put things in perspective, Gozo has a permanent population of around 40,000, with its capital city, Victoria, home to 6,500. Xewkija has just over 3,000 residents, yet in the early 1970s the villagers decided that their church wasn't big enough and so built a new one. The result is the Rotunda, a structure with one of the largest domes in Europe and a nave big enough to seat 4,000. And we could see it from our swimming pool.
The villa was upside down, so two of the bedrooms and a bathroom were on the ground floor, and everything else was upstairs - including the pool. So on our first morning we had woken up, flopped into the water and spent an hour gazing out over Gozo's version of St Paul's, sitting in the middle distance like a huge alien ship dropped from space. Over the next seven days we slipped into a vigorous morning routine: up, swim, stare, eat - followed by a bit of sightseeing or a trip to the beach. And at night we would lie out and chat in the dark with the dogs barking in the street below and the villagers gathered on their front steps to drink and eat and talk.
Gozo is one of those places where you quickly feel at home. It's tiny - at just nine miles by six, you can drive from one end to the other in half an hour. And after a brief trip through the chaotic streets of Malta (the locals say that Maltese drivers don't stick to either the left or right, they just drive in the shade) en route to Gozo, its empty streets were almost a shock to the system. It feels a bit like the land that time forgot - you're more likely to see a pristine Vauxhall Viva belching up a hill in a vain attempt to overtake a farmer on a sit-down lawn mower than anything as showy as a modern-day motor vehicle.
In the heat of the afternoon it was almost silent, and in the evenings things were barely livelier - of its 700,000 yearly visitors, only 42,000 sleep here. The rest come from Malta and are shipped back at sundown. One of Gozo's most arresting features is its colours. It may be just a short hop from the dusty plains of Tunisia, and just a few miles from its sun-bleached neighbour Malta, but it is a riot of shades thanks to its porous, clay-rich soils. Its roads are lined with pink, white and red oleander bushes; its valleys carpeted with vines, sunflowers, bamboo, prickly pears, fiery hibiscus, thyme, olive trees and citrus groves. Gozo's squat, sand-coloured limestone villages stand sentinel from the tops of its rocky hills, the odd cluster of houses scattered across the valleys in the heat-haze below. And surrounding this Impressionist's palette, visible from every summit, is the inky blue Mediterranean.
For such a small island, Gozo is full of surprises. Huge churches are not unusual, no matter how small the village. It has what are claimed to be the oldest man-made structures on earth, the 5,500-year-old fertility temples of Ggantija. The waters around Gozo and its even smaller neighbour, Comino, are reputed to be the best in the Med for diving. It is also studded with forts and sea defences, having been presided over for a quarter of a millennia by the Knights of St John, the crusading medics who established hospitals and provided protection for pilgrims travelling the route from Rome to the Holy Lands. And Victoria has two opera houses but no hotels.
The extravagant churches and generous collection of music venues are the result of the Gozitans' competitiveness. The story goes that the islanders are so partisan that they will form allegiances to anything - from football teams (half follow England, the other half Italy) to patron saints (the opera houses were built by "supporters" of St Mary and St George). Once the first one went up, the churchgoers just a couple of hundred yards up the road decided they wanted one too, and theirs had to be bigger and better.
Gozo might be sleepy for most of the year, but its villages wake up every summer to stage festas (festivals) in honour of their patron saints. The streets are blocked off and wrapped in bunting, statues are brought out to line the pavements and the square is given over to a stage for singing and dancing. We spent a couple of evenings at the festa in St Lawrenz in western Gozo, and it was quite a sight. The brass band that came parping through town was so big it could have staffed three collieries, and at night the fireworks were loud enough to shake the windows of our hotel room - if they'd exploded near our flat in London, all the car alarms over a half-mile radius would have gone into meltdown.
By day we discovered the charms of the surrounding area - including the impressive church of Ta'Pinu, Gozo's most sacred shrine. It attained this status when, in the 1920s, a parishioner heard a voice telling her she had to go to the church and pray, as she would not be able to go again for a year. The woman fell ill the very next day, and ever since the site has been credited with performing miracles.
The building itself follows the island's architectural traditions - tons of perfectly crafted limestone and improbably high ceilings - but it is in an annexe that Ta'Pinu's fascinating history is revealed. The walls are covered with bizarre items - a child's back brace, crutches, combat medals, motorbike helmets - each accompanied by a touching, and often funny, letter from the grateful whose prayers were answered. The tales range from the death-defying, like that of the Maltese security guard at the World Trade Center who was guided to safety on 11 September by a statue of the Virgin he brought with him from Ta'Pinu - to the more everyday - such as the story of the woman whose grandson swallowed a marble, which now sits in a glass case with her thanks for saving him from surgery.
If we were loosening up after the week in the villa, by the time we went home we had almost completely unravelled. The second week of our trip was spent at the five-star Kempinski St Lawrenz, a 120-room limestone retreat with one of Europe's top ayurvedic spas tucked away inside. Ayurveda is an ancient Indian holistic therapy that claims to tackle conditions as diverse as stress, eczema and infertility, and the Kempinski's team was brought to Gozo en masse from Kerala.
Laura was booked in for three days of pre-natal treatments, which included massages with oils and spices that are shipped to the island from India every three months. After checking in, we settled into our second exhausting routine of the holiday - get up, eat an extravagant breakfast (most treatment courses come with a special diet, but as we were only there for three days Laura was given dispensation to eat pastries) and then spend the morning apart - me by the pool with a book, Laura being kneaded in an air-conditioned room. After the first day she arrived back to meet me in a fluffy white dressing gown, beaming like someone who'd been hypnotised. She then had to go back to the room to sleep for the next hour and a half.
I decided to see what all the fuss was about, so went for a consultation with the centre's chief practitioner, Dr Vijayakumar. He stared at my eyes and tongue, felt my pulse, and quizzed me about my lifestyle and, strangely, my receding hairline. That afternoon an envelope dropped through our door containing a diet plan that would cure my sleep problems and help me cope with stress. It seems that all the things I like (red meat, pasta, alcohol, bananas) are off limits and I should learn to survive on white meat, dried apricots and pulses (plus plenty of other healthy items - the list took up three pages). And if it meant being able to stay in Gozo for any longer, I'd do it.
It had been the perfect place for us both to rest in preparation for the sleepless nights that were just around the corner, and all our pre-trip boxes had been ticked. Relaxation? Yes. Sea? Like glass. And the weather was glorious. Every day.
The writer flew to Malta with Air Malta (08456 073 710; www.airmalta.com); the island is also served by GB Airways (0870 850 9850; www.gbairways.com) and Excel Airways (08703 207 777; www.xl.com). To reduce the impact on the environment, you can buy an "offset" from Climate Care (01865 207 000; www.climatecare.org). The environmental cost of a return flight from London to Malta, in economy class, is £3.50. The money is used to fund sustainable energy and reforestation projects. Helicopters from Malta's airport at Luqa to Gozo are operated by HSE (00 356 2156 1301; www.airgozo.com). The standard return fare is LM50 (£83). Ferries operated by Gozo Channel Line ( www.gozochannel.com) sail to Gozo every 45 minutes during the day from Cirkewwa, with a journey time of under half-an-hour. The passenger fare is LM2 (£3.30) northbound (or LM6.75/£10 per person with a car), but the ferry is free southbound.
The writer stayed at Villa Bugzy in Nadur, one of several properties offered by Meon Villas (0870 909 7550; www.meonvillas.co.uk). One week's rental of the villa, which sleeps six, costs from £669 per week. Meon can also organise flights and car hire.
Kempinski Hotel St Lawrenz, Triq ir-Rokon, San Lawrenz (00 356 2211 0000; www.kempinski-gozo.com). Doubles start at LM60 (£94), including breakfast.
Two of the best restaurants are Ta'Frenc (00 356 2155 3888; www.tafrencrestaurant.com) between Victoria and Marsalforn, and the Il Barakka fish restaurant (bookings can be made at Gleneagles Bar) in Mgarr.
Gozo features as part of the latest Independent Traveller podcast, on Malta, published today; listen or download the programme at www.independent.co.uk/travel.
Malta Tourist Office: 020-8877 6990; www.visitmalta.com