OLAP is not just MOLAP!
Like very many articles on the subject, you use the acronym OLAP when you are actually talking about MOLAP i.e. multi-dimensional OLAP. There are other forms of OLAP such as relational OLAP (ROLAP) and hybrid OLAP (HOLAP) out there as well...but you knew that :-)
In addition to presenting a conceptually multi-dimensional view of the data to the business user, the MOLAP approach differs from the relational approach in two key areas - data aggregation and the the (normally partial) pre-calculation of query results.
It is as a result of aggregation and results pre-calculation that we get the speed up when compared to a relational system. As you point out this speed up is traded against the query flexibility offered by the 'go anywhere' relational schema.
The majority of queries are from 'farmers' rather than 'explorers', and this group can normally be provided with access to a series of MOLAP cubes that support the predictable KPI style reports that they run repeatedly. Explorers are more typically provided with access to detail level data in the relational schema.
Interestingly, it is OLAP users themselves that cite consistently fast queries as by far and away the most important benefit of delpoying a MOLAP solution. In fact, it is cited as more important than all other benefits combined, if the OLAP Report is to be believed, and I have no reason not to!