Carlos the guard gets on to the intercom. "Can I have your attention please," he asks, after the train comes to a sudden halt in what seems to be the middle of an olive grove in the middle of nowhere. "We are just about to change the wheels." The English passengers aboard our service from Madrid to Granada are looking understandably anxious. Leaves on the line or the wrong kind of snow are one thing. But the wheels coming off somewhere in remote Andalucia?
Welcome to the train in Spain. With much hissing and clanking and dinging of bells as locomotives are changed, we are drawn through a corrugated metal shed. Here the carriages are eased through nearly two centuries of railway history as a machine alters the width of the axles, while we sit in our seats watching Sarah Jessica Parker in I Don't Know How she Does It on the screen above us.
In the entrails of the coach, somewhere beneath us, we are being switched from the international gauge of 4ft 81/2in, defined by Britain's own Robert Stephenson, to Spain's almost unique broad gauge of 5ft 52/3in, based on old Castilian units of measurement. It was reputedly designed to prevent invasion by the French, in the days when such things mattered.
But the Heath Robinson contraption is far from a measure of the slowness of Spanish trains. On the contrary, it shows how fast they are changing. Soon we are back at speed on our way to Granada, where using the railway is by far the most civilised way to travel between here and the other great Moorish cities of southern Spain: Seville and Cordoba.
Gone are the days when international passengers had to change trains and trudge off with heavy luggage at the French border. This old-fashioned world was characterised by the old Iberian railway joke: "A peasant who took the daily train to market is seen one morning getting his donkey ready instead. Asked if he has decided to forsake the railway, he replies: 'Oh, no. It's just that I'm in a bit of hurry today!'"
Now new technology has put Spain at the forefront of international high-speed rail development – a far cry from the world described in Jan Morris's book Spain, written in the 1960s when splendid "brass-bound locomotives snorted in steam and metal polish down Spanish railways" past hay carts rumbling down lanes with "bullocks sweating in the shafts and yokels in straw hats hanging on behind".
Who would guess that the country has the world's biggest mileage of dedicated high-speed lines outside China, leaving even France's iconic TGVs lagging behind? While Britain bickers over whether to build its first domestic high-speed line over the modest 100 miles between London and Birmingham, the Spanish are celebrating this year the 20th anniversary of high-speed rail, thanks to the vision (or, some might say, self-interest and access to massive euro loans) of Felipe González, Spain's first Andalucian prime minister. He launched Spain's first high-speed line from Madrid to his native city of Seville in 1992.
Here in Andalucia, the most sensuous region of Spain – land of bullfights, flamenco, Moorish castles and strong sherry – the elegant high-speed AVE trains (the initials stand for "Alta Velocidad Española", with ave also conveniently meaning "bird") seem in almost perfect harmony with their environment. Sleek new bridges and viaducts punctuate an ancient landscape of olive, fig and orange trees, while the glinting snow-covered crests of the Sierra Nevada remain a constant companion on the skyline. Despite speeds of up to 186mph, the view through the window is a natural match with these wide empty horizons where the landscape never seems blurred or cluttered.
As the train zips me from Seville to Cordoba in just 42 minutes (Granada is another two hours 20 minutes along the line), the words of Paul Theroux, that most eminent of railway travellers, come to mind. Written in another context, but no less apt here, Theroux describes his railway idyll as "nothing in the world more restful; the train seemed like the highest stage of civilisation. Nothing was disturbed by it, or spoiled. It did not alter the landscape; it was the machine in the garden, but it was a gentle machine. It was fast and economical and safe as a vehicle could be".
And unlike any other form of transport, the high-speed trains of Spain deliver you effortlessly into the heart of Andalucia's magnificent Moorish cities. From the centrally placed stations in the hearts of Seville, Cordoba and Granada, it is possible walk almost everywhere, liberated from the hire cars tussling with each other along medieval lanes or tour buses belching fumes into historic squares.
Here, it seems to me, is a near-perfect symbiosis between fast and slow travel. While you may not rival Laurie Lee, who famously strode across the region in 1935, later recounted in his book As I Walked Out One Midsummer Morning, all you need to get into the heart of the real Andalucia is a ticket for the fast train and a decent pair of shoes so you can slow down when you get there.
I ponder on the intimacy with people and landscape that this combination of train and foot travel almost uniquely provides as I walk from the station in Granada, clambering up a steep cobbled pathway to the Alhambra palace. There is barely a soul to be seen on this secluded climb, fragrant with jasmine and almond blossom, to one of the most visited buildings in the world.
The only sounds are birdsong and the gentle rustling of a track-side stream. Yet, on the other side of the hill, near the main road entrance, the crowds seem like match day at Real Madrid, with queues of bemused tourists extending as far as the eye can see.
There are similar parallel universes to be entered almost everywhere in these Andalucian cities – wherever your feet can take you, sidestepping what someone once called the "tourist pilgrimages of mass consumption" and lingering longer in the byways and backwaters.
In Seville's main square, grim-faced sightseers endure the queue for the massive cathedral – the largest church in the world according to a certificate displayed inside. But it is scarcely a spiritual experience, elbowing through the iPhone-toting gawpers thronged around Christopher Columbus's tomb. Yet, a short walk away, along cobbled streets scarcely wide enough for a moped to pass, I push the door of a dilapidated baroque convent and slip into a chapel, entirely deserted, except for a group of black-clad nuns singing sweetly behind a grille. In the recesses of the high ceiling, two tiny yellow birds flutter around as if ordained by the Almighty.
Opposite the cathedral gates, where the tourists queue for frappuccinos and muffins at Starbucks, a dip into the narrow streets of Santa Cruz, beyond the archbishop's palace, will take you to the Cerveceria Giralda, a dark and cool former Moorish bathhouse, where you can take tapas of aguacate relleno de merluza (avocado stuffed with hake) or pastel de champiñones (mushroom tart) with a glass of delicious local manzanilla – reputed never to give you a hangover.
The authentic Cordoba offers equal delights for backstreet wanderers, especially in the medieval Jewish quarter. In the Casa de Sefarad, an old house on a side street dedicated to the history of the Jews in the city – who lived harmoniously alongside their Muslim rulers at a time when Cordoba was the most cultured place in the world – the custodian tells me that once tens of thousands of Jews lived here. "Now, there are only 12 Jewish families. But do you know," he confides, "there are those who think Christopher Columbus was a Jew."
Granada, though, is the ultimate paradise for foot travellers, especially those willing to penetrate the maze of alleys around the old gypsy area of Sacromonte, high on the hillside. Here you can experience that pleasant tingle of getting lost, of discovering a view through a gate or at the end of an alley that you will almost certainly never be able to retrieve again, no matter how hard you try. Here are the drifting strains of flamenco from a guitar school, there the whiff of garlic through an open doorway. Everywhere on the whitewashed cobbled streets and all around you there seem to be flowers – orange marigolds, scarlet geraniums, creamy stephanotis – in pots nailed to outside walls, in overflowing tubs, in patios of walled gardens.
As for the Alhambra, there's no avoiding the crowds in the Nasrid Palaces, home to the last Moorish rulers in Spain, and reckoned by some to be the most sensuous buildings in the world. Take advantage of the fact that the tickets are timed. In the ellipsis between the first tranche of visitors hoofing their way through and the next crowd being let in, you can find yourself deliciously alone in some tranquil courtyard. Or by a fountain in the harem, almost expecting, like the 19th-century travel writer Washington Irving in his Tales of the Alhambra, "to see the white arm of some mysterious princess beckoning from the gallery or some dark eye sparkling through the lattice".
But the idyll must end. Sadly, I don't have the time for the comfortable rail journey back to London, which can now be achieved in no more than 20 hours, using the AVE and the delightful "train hotel" from Madrid to Paris. Instead, I aim for the airport in Malaga – a city, with its imposing new María Zambrano terminus that is also on the Spanish high-speed rail network. What a marvel, I think, as I browse through the glossy official rail guide. Eight new dedicated high-speed lines covering 1,400 milesreaching 19 regional capitals, with one of the most modern train fleets in the world; all built in just 20 years. But, hold on – there are only two direct services a day from Granada to Malaga.
It seems that to catch my flight I must take the early-morning bus from the local bus station and suddenly I am back in the old, anachronistic Spain of Jan Morris, where she reported that "Spanish country buses, bumpy and gregarious" had hardly changed since the age of the mail coach. Will I need to book in advance, I ask Victor, my hotel concierge? Will it be full? A shrug signifies a Spanish "maybe". "And, by the way, the bus company doesn't take overseas credit cards. You'll need to take a taxi there and back to the ticket office the day before to buy it in person."
But next time I see him, he produces my ticket with a flourish, having bought it himself. It is a reminder that, though speed might in some ways have changed Andalucia for ever, its old-fashioned courtesies endure. "This is Spain," says Victor. "What's the point in arguing with it?"
Seville is served from Gatwick by easyJet (0843 104 5000; easyjet.com) and Stansted by Ryanair (0871 246 0000; ryanair.com). Malaga is served by a wide range of airlines from the UK including easyJet, Ryanair, British Airways (0844 493 0787; ba.com), Monarch (0871 940 5040; monarch.co.uk), Jet2 (0871 226 1737; jet2.com) and FlyBe (0871 700 2000; flybe.com).
Michael Williams travelled as a guest of Inntravel (01653 617001; inntravel.co.uk) which offers “A Trail of Three Cities”, connecting by rail the Andalucian cities of Seville, Cordoba and Granada, with two nights spent in each, from £698 per person based on two sharing. The price includes six nights’ B&B, rail travel between cities, detailed documentation and walking tour notes, and city maps. Flights, or rail travel to and from the UK are not included.