The groundwork that allowed the use of the strait by the crusaders began much earlier than 1190, and has as much to do with other political and military developments around the Iberian peninsula than anything else. The Almohadin fleet had been for centuries a dominant force in the region, and has essentially controlled access to the Mediterranean for 400 years1. These were not by any stretch of the imagination "scrubby Arab lateens". In fact, the Muslim navies were among the first to move from coastal attacks to the open sea and were at the forefront of naval technology of the period. One naval historian writes,
This may have also encouraged the construction of bigger ships that
began to appear from the late 9th century onwards. By the 12th century
some vessels from Andalus could virtually barge their way through an
attempted Norman blockade of an Islamic port.2
He continues to note that these ships likely formed the basis for the later Italian and later Portuguese carracks3, and influenced European naval technology much in a way similar to architectural technology. By contrast, the dominance of the Muslims over the strait had a direct effect on the long term strategy and tactics of the crusades. It was known much earlier in the history of the crusades that controlling coastal access was crucial when fleets were mainly tied to the coast4, and this steered long term strategies in the Iberian - including the capture of Silves in 1188 (and a couple decades later the campaign to seize Gibraltar itself). Silves was one of the main nautical centers of the Moors in the Iberian, and its loss had far reaching effects even beyond the crusades, jump-starting Portuguese naval development5. It was this groundwork (along with the hard learned recognition of the need for maritime logistical support) that allowed the Richard to consider sending a large fleet through the strait.
The other piece of the puzzle is situation of of the Almohads at the time. As other posters point out, at the time of the third crusade they were basically fighting several wars at the same time. There was the ongoing conflict with the Portuguese and Spanish in Iberia, they were at war with Saladin, and by 1180 they were in enough of a decline that their power over the strait had been severely curtailed.
We must remember that by 1180 the Almohadin, a true medieval naval
superpower, were fighting on three fronts: It was not a winnable war.
Everyone wanted the Strait. Specifically, the former Taifa
Kingdom-City of Silves gave the Crusaders a direct approach to the
Atlantic Straits and, in conjunction with the Anglo/Italian-held
Tortosa as an exit, and with Sicilian suppression of the Barbary coast
from the direction of Tunisia, having Atlantic Silves allowed the
Crusaders direct transit not only through the Straits but through the
very heart of the Almohad Empire.6
So if "Richard was a lot more afraid of storms", it was because control of the strait by the Almohadin had been compromised by 1190. They neither had the inclination nor available military capacity to attempt to stop Richard's fleet.
Note: Just an aside, Richard didn't actually sail with the fleet through the Strait - he marched overland from Vézelay with the intention of meeting them in Marseille. Due to a drunken pillaging of Lisbon that resulted in a 3 week delay, Richard had already left without them on hired ships.7
1Truver, Scott. The Strait of Gibraltar And the Mediterranean, p 162
2Nicolle, David. The Moors: The Islamic West 7th-15th Centuries AD, p 19
3Ibid, p 20
4France, John. "The First Crusade as Naval Enterprise", The Mariner's Mirror Nov 1997, p 392
5Nicolle, David. The Third Crusade 1191: Richard the Lionheart, Saladin and the Struggle for Jerusalem, p 42
6Cushing, Dana. The Qadi of Xelb in the Third Crusade (Silves 1189), p 3
7Gillingham, John, Richard I, p 129-30